各種排序算法總結(jié)(C語言版)

1、6.1 常見的排序算法常見的排序算法 冒泡排序 快速排序直接插入排序 希爾排序 選擇排序 堆排序歸并排序 6.1.1 冒泡排序冒泡排序算法描述設(shè)待排序記錄序列中的記錄個數(shù)為n一般地，第i趟起泡排序從1到n-i+1依次比較相鄰兩個記錄的關(guān)鍵字，如果發(fā)生逆序，則交換之其結(jié)果是這n-i+1個記錄中，關(guān)鍵字最大的記錄被交換到第n-i+1的位置上，最多作n-1趟。6.1.1 冒泡排序冒泡排序算法實(shí)例0 1 2 3 4 56.1.1 冒泡排序冒泡排序算法實(shí)例0 1 2 3 4 56.1.1 冒泡排序冒泡排序算法實(shí)例初始關(guān)鍵字第一趟排序第四趟排序第二趟排序第三趟排序第五趟排序6.1.1 冒泡排序冒泡排序算法

2、實(shí)現(xiàn)輸入n 個數(shù)給a1 到 anfor j=1 to n-1for i=1 to n-jaiai+1真假aiai+1輸出a1 到 an#include main() int a11,i,j,t; printf(Input 10 numbers:n); for(i=1;i11;i+) scanf(%d,&ai); printf(n); for(j=1;j=9;j+) for(i=1;iai+1) t=ai; ai=ai+1; ai+1=t; printf(The sorted numbers:n); for(i=1;i11;i+)printf(%d ,ai);6.1.2 快速排序快速排序

3、 算法特點(diǎn)：快速排序是通過比較關(guān)鍵碼、交換記錄，以某個記錄為界(該記錄稱為支點(diǎn))，將待排序列分成兩部分一部分所有記錄的關(guān)鍵碼大于等于支點(diǎn)記錄的關(guān)鍵碼另一部分所有記錄的關(guān)鍵碼小于支點(diǎn)記錄的關(guān)鍵碼 6.1.2 快速排序快速排序 算法描述：任取待排序記錄序列中的某個記錄(例如取第一個記錄)作為基準(zhǔn)(樞),按照該記錄的關(guān)鍵字大小,將整個記錄序列劃分為左右兩個子序列左側(cè)子序列中所有記錄的關(guān)鍵字都小于或等于基準(zhǔn)記錄的關(guān)鍵字 右側(cè)子序列中所有記錄的關(guān)鍵字都大于基準(zhǔn)記錄的關(guān)鍵字基準(zhǔn)記錄則排在這兩個子序列中間(這也是該記錄最終應(yīng)安放的位置)。然后分別對這兩個子序列重復(fù)施行上述方法，直到所有的記錄都排在相應(yīng)位置上

4、為止?；鶞?zhǔn)記錄也稱為樞軸（或支點(diǎn)）記錄。取序列第一個記錄為樞軸記錄，其關(guān)鍵字為Pivotkey指針low指向序列第一個記錄位置指針high指向序列最后一個記錄位置6.1.2 快速排序快速排序 算法實(shí)例：始關(guān)鍵字始關(guān)鍵字pivotkey一次交換一次交換二次交換二次交換三次交換三次交換high-1完成一趟排序完成一趟排序lowhighlowlowlowlowlowhighhighhighhighhigh6.1.2 快速排序快速排序 算法實(shí)例：10完成一趟排序完成一趟排序分別進(jìn)行快速排序分別進(jìn)行快速排序有序序列有序序列6.1.2 快速排序快速排序 算法分析：快速排序是一個遞歸過程;利用序列第一個記錄

5、作為基準(zhǔn)，將整個序列劃分為左右兩個子序列。只要是關(guān)鍵字小于基準(zhǔn)記錄關(guān)鍵字的記錄都移到序列左側(cè)；快速排序的趟數(shù)取決于遞歸樹的高度。如果每次劃分對一個記錄定位后, 該記錄的左側(cè)子序列與右側(cè)子序列的長度相同, 則下一步將是對兩個長度減半的子序列進(jìn)行排序, 這是最理想的情況 116.1.3 直接插入排序直接插入排序 算法描述：記錄存放在數(shù)組R0.n-1中，排序過程的某一中間時刻，R被劃分成兩個子區(qū)間R0i-1和Ri.n-1，其中：前一個子區(qū)間是已排好序的有序區(qū)；后一個子區(qū)間則是當(dāng)前未排序的部分?；静僮鲗?dāng)前無序區(qū)的第1個記錄Ri插入到有序區(qū)R0.i-1中適當(dāng)?shù)奈恢茫筊0i變?yōu)樾碌挠行騾^(qū) 6.1.3

6、 直接插入排序直接插入排序 操作細(xì)節(jié)：當(dāng)插入第當(dāng)插入第i(i1)i(i1)個對象時個對象時, , 前面的前面的r0, r1, r0, r1, , ri-1, ri-1已經(jīng)排已經(jīng)排好序。好序。用用riri 的關(guān)鍵字與的關(guān)鍵字與ri-1, ri-2, ri-1, ri-2, 的關(guān)鍵字順序進(jìn)行比較的關(guān)鍵字順序進(jìn)行比較( (和順和順序查找類似序查找類似) )，如果小于，則將，如果小于，則將rxrx 向后移動向后移動( (插入位置后的記錄向插入位置后的記錄向后順移后順移) )找到插入位置即將找到插入位置即將riri 插入插入6.1.3 直接插入排序直接插入排序 實(shí)用例子：已知待序的一組記錄的初始排列為：

7、已知待序的一組記錄的初始排列為：21, 25, 49, 2521, 25, 49, 25* *, 16, 08, 16, 080 1 2 3 4 56.1.3 直接插入排序直接插入排序 實(shí)用例子：0 1 2 3 4 5 temp2525250 1 2 3 4 5 temp494949252525* * *0 1 2 3 4 56.1.3 直接插入排序直接插入排序 實(shí)用例子：0 1 2 3 4 5 temp1616160 1 2 3 4 5 temp0808080 1 2 3 4 5完成6.1.3 直接插入排序直接插入排序 算法實(shí)現(xiàn)：void InsertSort (int r , int n

8、) / 假設(shè)關(guān)鍵字為整型，放在向量假設(shè)關(guān)鍵字為整型，放在向量r中中 int i, j, temp; for (i = 1;i0;j- -) /從后向前順序比較，并依次后移從后向前順序比較，并依次后移 if ( temp rj-1 ) rj = rj-1; else break; rj = temp; 6.1.3 直接插入排序直接插入排序 算法分析：關(guān)鍵字比較次數(shù)和記錄移動次數(shù)與記錄關(guān)鍵字的初始排列有關(guān)。最好情況下, 排序前記錄已按關(guān)鍵字從小到大有序, 每趟只需與前面有序記錄序列的最后一個記錄比較1次, 移動2次記錄, 總的關(guān)鍵字比較次數(shù)為 n-1, 記錄移動次數(shù)為 2(n-1)在平均情況下的關(guān)

9、鍵字比較次數(shù)和記錄移動次數(shù)約為 n2/4。直接插入排序是一種穩(wěn)定的排序方法直接插入排序最大的優(yōu)點(diǎn)是簡單，在記錄數(shù)較少時，是比較好的辦法6.1.4 希爾排序希爾排序 希爾排序又稱縮小增量排序是1959年由D.L.Shell提出來的 算法描述先取定一個小于n的整數(shù)d作為第一個增量，把表的全部記錄分成d組所有距離為d1的倍數(shù)的記錄放在同一組中，在各組內(nèi)進(jìn)行直接插入排序然后取第二個增量d2d1重復(fù)上述的分組和排序，直至增量d1，即所有記錄放在同一組中進(jìn)行直接插入排序?yàn)橹埂?6.1.4 希爾排序希爾排序 算法特點(diǎn)先取定一個小于n的整數(shù)d作為第一個增量，把表的全部記錄分成d組所有距離為d1的倍數(shù)的記錄放在

10、同一組中，在各組內(nèi)進(jìn)行直接插入排序然后取第二個增量d2d1重復(fù)上述的分組和排序，直至增量d1，即所有記錄放在同一組中進(jìn)行直接插入排序?yàn)橹埂?6.1.4 希爾排序希爾排序 運(yùn)用實(shí)例先取定一個小于n的整數(shù)d作為第一個增量，把表的全部記錄分成d組所有距離為d1的倍數(shù)的記錄放在同一組中，在各組內(nèi)進(jìn)行直接插入排序然后取第二個增量d2d1重復(fù)上述的分組和排序，直至增量d1，即所有記錄放在同一組中進(jìn)行直接插入排序?yàn)橹埂?6.1.4 希爾排序希爾排序 希爾排序又稱縮小增量排序是1959年由D.L.Shell提出來的 算法描述首先取一個整數(shù) gap n(待排序記錄數(shù)) 作為間隔, 將全部記錄分為 gap 個子序

11、列, 所有距離為 gap 的記錄放在同一個子序列中在每一個子序列中分別施行直接插入排序。然后縮小間隔 gap, 例如取 gap = gap/2重復(fù)上述的子序列劃分和排序工作，直到最后取gap = 1, 將所有記錄放在同一個序列中排序?yàn)橹埂?.1.4 希爾排序希爾排序 運(yùn)用實(shí)例已知待排序的一組記錄的初始排列為：已知待排序的一組記錄的初始排列為：21, 25, 49, 2521, 25, 49, 25* *, 16, 08, 16, 080 1 2 3 4 5 6.1.4 希爾排序希爾排序 運(yùn)用實(shí)例t 30 1 2 3 4 50 1 2 3 4 5t 2t 16.1.4 希爾排序希爾排序 算法分析

12、開始時 gap 的值較大, 子序列中的記錄較少, 排序速度較快隨著排序進(jìn)展, gap 值逐漸變小, 子序列中記錄個數(shù)逐漸變多,由于前面大多數(shù)記錄已基本有序, 所以排序速度仍然很快Gap的取法有多種。 shell 提出取 gap = n/2，gap = gap/2，直到gap = 1。6.1.5 選擇排序選擇排序 排序過程：排序過程：首先通過首先通過n-1次比較，從次比較，從n個數(shù)中找出最小的，個數(shù)中找出最小的， 將它與第一個數(shù)將它與第一個數(shù) 交換交換第一趟選擇排序，結(jié)果最小的數(shù)被安置在第一個元素位第一趟選擇排序，結(jié)果最小的數(shù)被安置在第一個元素位置上置上再通過再通過n-2次比較，從剩余的次比較，

13、從剩余的n-1個數(shù)中找出關(guān)鍵字次小的記錄，個數(shù)中找出關(guān)鍵字次小的記錄，將它與第二個數(shù)交換將它與第二個數(shù)交換第二趟選擇排序第二趟選擇排序重復(fù)上述過程，共經(jīng)過重復(fù)上述過程，共經(jīng)過n-1趟排序后，排序結(jié)束趟排序后，排序結(jié)束6.1.5 選擇排序選擇排序 排序?qū)嵗号判驅(qū)嵗豪跏迹?49 38 65 97 76 13 27 kji=11349一趟： 13 38 65 97 76 49 27 i=22738二趟： 13 27 65 97 76 49 38 三趟： 13 27 38 97 76 49 65 四趟： 13 27 38 49 76 97 65 五趟： 13 27 38 49 65 97 76

14、六趟： 13 27 38 49 65 76 97 kkkkjjjjjjjjjj6.1.5 選擇排序選擇排序 算法實(shí)例：算法實(shí)例：0 1 2 3 4 56.1.5 選擇排序選擇排序 算法實(shí)例：算法實(shí)例：0 1 2 3 4 5最小者最小者最小者最小者各趟排序后的結(jié)果各趟排序后的結(jié)果6.1.5 選擇排序選擇排序 算法實(shí)例：算法實(shí)例：0 1 2 3 4 5i =2時選擇排序的過程時選擇排序的過程i k j i k j i k j 6.1.5 選擇排序選擇排序 算法實(shí)例：算法實(shí)例：0 1 2 3 4 5i k j 6.1.5 選擇排序選擇排序 算法實(shí)現(xiàn)：算法實(shí)現(xiàn)：輸入n 個數(shù)給a1 到 anfor i=

15、1 to n-1for j=i+1 to najak真假k=j輸出a1 到 ank=iaiaki != k真假#include main() int a11,i,j,k,x; printf(Input 10 numbers:n); for(i=1;i11;i+) scanf(%d,&ai); printf(n); for(i=1;i10;i+) k=i; for(j=i+1;j=10;j+) if(ajak) k=j; if(i!=k) x=ai; ai=ak; ak=x; printf(The sorted numbers:n); for(i=1;i11;i+)printf(%d ,ai);階段小節(jié)階段小節(jié) 幾種常見的排序算法 冒泡排序的特點(diǎn) 快速排序的特點(diǎn)，一趟排序的子過程本章總結(jié)本章總結(jié)數(shù)據(jù)結(jié)構(gòu)與算法初步數(shù)據(jù)結(jié)構(gòu)與算