五大基本排序算法

1、一. 選擇排序算法：算法基本原理：一次選定數(shù)組中的每一個(gè)數(shù)，記下當(dāng)前位置并假設(shè)它是從當(dāng)前位置開始后面數(shù)中的最小數(shù)min=i，從這個(gè)數(shù)的下一個(gè)數(shù)開始掃描直到最后一個(gè)數(shù)，并記錄下最小數(shù)的位置min，掃描結(jié)束后如果min不等于i，說明假設(shè)錯(cuò)誤，否則交換min與i位置上數(shù)。算法實(shí)現(xiàn)：#include /選擇排序，如果第一個(gè)數(shù)字小于后面的則向后移動(dòng)，依次類推該排序時(shí)不穩(wěn)定的，時(shí)間復(fù)雜度是N平方void main()int array10 = 112,4,2,3,5,33,6,7,8,9;/定義一個(gè)數(shù)組int length = sizeof(array)/sizeof(array0);/得到數(shù)組的長度in

2、t k=0, s=0, i=0, j=0;/k保存臨時(shí)結(jié)果，s，i，j為循環(huán)變量/選擇排序開始for(i=0;ilength;i+)for(j=i+1;jarrayj)k=arrayi;arrayi=arrayj;arrayj=k;/選擇排序結(jié)束，輸出顯示排序的結(jié)果for(s=0; slength; s+)printf(%d n,arrays);二.冒泡排序算法基本原理：對(duì)尚未排序的各元素從頭到尾依次比較相鄰的兩個(gè)元素是否逆序（與欲排順序相反），若逆序就交換這兩元素，經(jīng)過第一輪比較排序后便可把最大（或最?。┑脑嘏藕茫缓笤儆猛瑯拥姆椒ò咽Ｏ碌脑刂饌€(gè)進(jìn)行比較，就得到了你所要的順序。算法實(shí)現(xiàn)：

3、#include /冒泡排序,開始的時(shí)候兩個(gè)數(shù)進(jìn)行比較，大的向后小的向前，第一次比較很容易的就把最大的一個(gè)數(shù)字放到了最后小的呢，繼續(xù)向前，第二次當(dāng)然也找到了第二個(gè)大的，放到倒數(shù)第二的位置，如此下去便可。這個(gè)是優(yōu)化的冒泡排序方法，讓k=j保存最后的那個(gè)數(shù)的下標(biāo)，這樣k后面的數(shù)都是排序好的了,這個(gè)排序是穩(wěn)定的，時(shí)間復(fù)雜度是N平方void main()int array10 = 1,2,11,22,33,4,23,234,4,6;int length = sizeof(array)/sizeof(array0);int k=0, s=0, i=0, j=0, m=0;/冒泡排序開始for(i = l

4、ength-1;i0;i=k)for(j=0, k=0;jarrayj+1)/把比較出來大的數(shù)據(jù)向后移動(dòng)m=arrayj;arrayj=arrayj+1;arrayj+1=m;k=j;/冒泡排序結(jié)束，輸出顯示排序的結(jié)果for(s=0; slength; s+)printf(%d n,arrays);三.快速排序算法基本原理：快速排序（Quicksort）是對(duì)冒泡排序的一種改進(jìn)。由C. A. R. Hoare在1962年提出。它的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程

5、可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。算法實(shí)現(xiàn)：#include /快速排序開始，使用遞歸方法，取其中一個(gè)數(shù)（任意基本上都是以第一個(gè)為準(zhǔn)），先從后面比較，如果這個(gè)數(shù)比后面的大交換之，如果不大繼續(xù)比較直到大為止，如果大，則交換之，再到前面比較，如果前面的比這個(gè)數(shù)小交換之再和后面的比較，第一趟下來比它小的就在前面了，比它大的就在后面嘍，然后再把該數(shù)組分成兩部分使用遞歸，直到最后排序完成void paixu(int array, int low, int hight)int i,j,t,m;if(lowhight)i = low;j = hight;t = arraylow;while(ij)

6、while(it)/開始和后面的比較，如果后面的比他大繼續(xù)，如果后面的比它小交換之j-;if(ij)/在沒有越界（i是從前面開始，j是從后面開始）的情況下進(jìn)行交換m=arrayi;arrayi=arrayj;arrayj=m;i+;/讓前面的向后移動(dòng)一個(gè)繼續(xù)比較while(ij & arrayi=t)/和前面的比較，如果前面的小于等于該關(guān)鍵數(shù)據(jù)繼續(xù)，如果大于交換之i+;if(ij)m=arrayj;arrayj=arrayi;arrayi=m;j-;arrayi=t;/第一次比較結(jié)束，把i放到中間的位置，也即在i前面都比i小，在i后面都比i大paixu(array, low, i-1);/前面

7、部分實(shí)現(xiàn)遞歸paixu(array, i+1, hight);/后面部分實(shí)現(xiàn)遞歸void main()int s=0;int array = 10,22,3,21,45,67,2,11,110,453;int length = sizeof(array)/sizeof(array0);paixu(array,s,length-1);for(s=0;slength;s+)printf(%d n,arrays);四.插入排序有一個(gè)已經(jīng)有序的數(shù)據(jù)序列，要求在這個(gè)已經(jīng)排好的數(shù)據(jù)序列中插入一個(gè)數(shù)，但要求插入后此數(shù)據(jù)序列仍然有序，這個(gè)時(shí)候就要用到一種新的排序方法插入排序法,插入排序的基本操作就是將一個(gè)數(shù)據(jù)

8、插入到已經(jīng)排好序的有序數(shù)據(jù)中,從而得到一個(gè)新的、個(gè)數(shù)加一的有序數(shù)據(jù)，算法適用于少量數(shù)據(jù)的排序，時(shí)間復(fù)雜度為()。是穩(wěn)定的排序方法。插入算法（insertion sort）把要排序的數(shù)組分成兩部分：第一部分包含了這個(gè)數(shù)組的所有元素，但將最后一個(gè)元素除外，而第二部分就只包含這一個(gè)元素。在第一部分排序后，再把這個(gè)最后元素插入到此刻已是有序的第一部分里的正確位置中。包括：直接插入排序，折半插入排序，鏈表插入排序，Shell排序算法基本原理：假定這個(gè)數(shù)組的序是排好的,然后從頭往后,如果有數(shù)比當(dāng)前外層元素的值大,則將這個(gè)數(shù)的位置往后挪,直到當(dāng)前外層元素的值大于或等于它前面的位置為止.這具算法在排完前k個(gè)數(shù)

9、之后,可以保證a1k是局部有序的,保證了插入過程的正確性.算法描述：一般來說，插入排序都采用in-place在數(shù)組上實(shí)現(xiàn)。具體算法描述如下：1. 從第一個(gè)元素開始，該元素可以認(rèn)為已經(jīng)被排序2. 取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描3. 如果該元素（已排序）大于新元素，將該元素移到下一位置4. 重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置5. 將新元素插入到該位置中6. 重復(fù)步驟2如果比較操作的代價(jià)比交換操作大的話，可以采用二分查找法來減少比較操作的數(shù)目。該算法可以認(rèn)為是插入排序的一個(gè)變種，稱為二分查找排序。算法實(shí)現(xiàn)：#include void main()int ar

10、ray = 9,43,567,1,45,23,123,54,234,987;int length = sizeof(array)/sizeof(array0);int i,j,t,m;/插入排序開始for(i=1;i0)&(arrayj-1t)/如果前面的數(shù)比它大交換之m=arrayj-1;arrayj-1=arrayj;arrayj=m;j-;/交換完畢繼續(xù)比較/插入排序結(jié)束for(i=0;ilength;i+)printf(%d n,arrayi);五.希爾排序希爾排序是基于插入排序的一種算法，在此算法基礎(chǔ)之上增加了一個(gè)新的特性，提高了效率。希爾排序的時(shí)間復(fù)雜度為 O(N*(logN)2)

11、， 沒有快速排序算法快 O(N*(logN)，因此中等大小規(guī)模表現(xiàn)良好，對(duì)規(guī)模非常大的數(shù)據(jù)排序不是最優(yōu)選擇。但是比O(N2）復(fù)雜度的算法快得多。并且希爾排序非常容易實(shí)現(xiàn)，算法代碼短而簡單。此外，希爾算法在最壞的情況下和平均情況下執(zhí)行效率相差不是很多，與此同時(shí)快速排序在最壞的情況下執(zhí)行的效率會(huì)非常差。專家門提倡，幾乎任何排序工作在開始時(shí)都可以用希爾排序，若在實(shí)際使用中證明它不夠快，再改成快速排序這樣更高級(jí)的排序算法. 本質(zhì)上講，希爾排序算法的一種改進(jìn)，減少了其復(fù)制的次數(shù)，速度要快很多。原因是，當(dāng)N值很大時(shí)數(shù)據(jù)項(xiàng)每一趟排序需要的個(gè)數(shù)很少，但數(shù)據(jù)項(xiàng)的距離很長。當(dāng)N值減小時(shí)每一趟需要和動(dòng)的數(shù)據(jù)增多，此

12、時(shí)已經(jīng)接近于它們排序后的最終位置。正是這兩種情況的結(jié)合才使希爾排序效率比插入排序高很多。在直接插入排序算法中，每次插入一個(gè)數(shù)，使有序序列只增加1個(gè)節(jié)點(diǎn)，并且對(duì)插入下一個(gè)數(shù)沒有提供任何幫助。如果比較相隔較遠(yuǎn)距離（稱為增量）的數(shù)，使得數(shù)移動(dòng)時(shí)能跨過多個(gè)元素，則進(jìn)行一次比較就可能消除多個(gè)元素交換。D.L.shell于1959年在以他名字命名的排序算法中實(shí)現(xiàn)了這一思想。算法先將要排序的一組數(shù)按某個(gè)增量d分成若干組，每組中記錄的下標(biāo)相差d.對(duì)每組中全部元素進(jìn)行排序，然后再用一個(gè)較小的增量對(duì)它進(jìn)行，在每組中再進(jìn)行排序。當(dāng)增量減到1時(shí)，整個(gè)要排序的數(shù)被分成一組，排序完成。下面的函數(shù)是一個(gè)希爾排序算法的一個(gè)實(shí)現(xiàn)，初次取序列的一半為增量，以后每次減半，直到增量為1。希爾排序是不穩(wěn)定的。算法實(shí)現(xiàn)：#include void main()int array = 1,445,754,77,35,123,754,876,54,3;int len