五大基本排序算法

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

2、t k=0, s=0, i=0, j=0;/k保存臨時結果，s，i，j為循環(huán)變量/選擇排序開始for(i=0;ilength;i+)for(j=i+1;jarrayj)k=arrayi;arrayi=arrayj;arrayj=k;/選擇排序結束，輸出顯示排序的結果for(s=0; slength; s+)printf(%d n,arrays);二.冒泡排序算法基本原理：對尚未排序的各元素從頭到尾依次比較相鄰的兩個元素是否逆序（與欲排順序相反），若逆序就交換這兩元素，經過第一輪比較排序后便可把最大（或最?。┑脑嘏藕?，然后再用同樣的方法把剩下的元素逐個進行比較，就得到了你所要的順序。算法實現：

3、#include /冒泡排序,開始的時候兩個數進行比較，大的向后小的向前，第一次比較很容易的就把最大的一個數字放到了最后小的呢，繼續(xù)向前，第二次當然也找到了第二個大的，放到倒數第二的位置，如此下去便可。這個是優(yōu)化的冒泡排序方法，讓k=j保存最后的那個數的下標，這樣k后面的數都是排序好的了,這個排序是穩(wěn)定的，時間復雜度是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)/把比較出來大的數據向后移動m=arrayj;arrayj=arrayj+1;arrayj+1=m;k=j;/冒泡排序結束，輸出顯示排序的結果for(s=0; slength; s+)printf(%d n,arrays);三.快速排序算法基本原理：快速排序（Quicksort）是對冒泡排序的一種改進。由C. A. R. Hoare在1962年提出。它的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程

5、可以遞歸進行，以此達到整個數據變成有序序列。算法實現：#include /快速排序開始，使用遞歸方法，取其中一個數（任意基本上都是以第一個為準），先從后面比較，如果這個數比后面的大交換之，如果不大繼續(xù)比較直到大為止，如果大，則交換之，再到前面比較，如果前面的比這個數小交換之再和后面的比較，第一趟下來比它小的就在前面了，比它大的就在后面嘍，然后再把該數組分成兩部分使用遞歸，直到最后排序完成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是從后面開始）的情況下進行交換m=arrayi;arrayi=arrayj;arrayj=m;i+;/讓前面的向后移動一個繼續(xù)比較while(ij & arrayi=t)/和前面的比較，如果前面的小于等于該關鍵數據繼續(xù)，如果大于交換之i+;if(ij)m=arrayj;arrayj=arrayi;arrayi=m;j-;arrayi=t;/第一次比較結束，把i放到中間的位置，也即在i前面都比i小，在i后面都比i大paixu(array, low, i-1);/前面

7、部分實現遞歸paixu(array, i+1, hight);/后面部分實現遞歸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);四.插入排序有一個已經有序的數據序列，要求在這個已經排好的數據序列中插入一個數，但要求插入后此數據序列仍然有序，這個時候就要用到一種新的排序方法插入排序法,插入排序的基本操作就是將一個數據

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

9、之后,可以保證a1k是局部有序的,保證了插入過程的正確性.算法描述：一般來說，插入排序都采用in-place在數組上實現。具體算法描述如下：1. 從第一個元素開始，該元素可以認為已經被排序2. 取出下一個元素，在已經排序的元素序列中從后向前掃描3. 如果該元素（已排序）大于新元素，將該元素移到下一位置4. 重復步驟3，直到找到已排序的元素小于或者等于新元素的位置5. 將新元素插入到該位置中6. 重復步驟2如果比較操作的代價比交換操作大的話，可以采用二分查找法來減少比較操作的數目。該算法可以認為是插入排序的一個變種，稱為二分查找排序。算法實現：#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)/如果前面的數比它大交換之m=arrayj-1;arrayj-1=arrayj;arrayj=m;j-;/交換完畢繼續(xù)比較/插入排序結束for(i=0;ilength;i+)printf(%d n,arrayi);五.希爾排序希爾排序是基于插入排序的一種算法，在此算法基礎之上增加了一個新的特性，提高了效率。希爾排序的時間復雜度為 O(N*(logN)2)

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

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