各種排序算法大全ppt課件

1、6.1 常見的排序算法常見的排序算法 冒泡排序 快速排序 直接插入排序 希爾排序 選擇排序 堆排序 歸并排序 6.1.1 冒泡排序冒泡排序 算法描畫 設(shè)待排序記錄序列中的記錄個(gè)數(shù)為n 普通地，第i趟起泡排序從1到n-i+1 依次比較相鄰兩個(gè)記錄的關(guān)鍵字，假設(shè)發(fā)生逆序，那么交換之 其結(jié)果是這n-i+1個(gè)記錄中，關(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 個(gè)數(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; printfInput 10 numbers:n; fori=1;i11;i+ scanf%d,&ai; printfn; forj=1;j=9;j+ fori=1;iai+1 t=ai; ai=ai+1; ai+1=t; printfThe sorted numbers:n; fori=1;i11;i+printf%d ,ai;6.1.2 快速排序快速排序 算法特點(diǎn)： 快

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

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

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

6、 直接插入排序直接插入排序 操作細(xì)節(jié)： 當(dāng)插入第ii1個(gè)對(duì)象時(shí), 前面的r0, r1, , ri-1曾經(jīng)排好序。 用ri的關(guān)鍵字與ri-1, ri-2, 的關(guān)鍵字順序進(jìn)展比較和順序查找類似，假設(shè)小于，那么將rx向后挪動(dòng)插入位置后的記錄向后順移 找到插入位置即將ri插入6.1.3 直接插入排序直接插入排序 適用例子： 待序的一組記錄的初始陳列為：21, 25, 49, 25*, 16, 080 1 2 3 4 56.1.3 直接插入排序直接插入排序 適用例子：0 1 2 3 4 5 temp250 1 2 3 4 5 temp4925*0 1 2 3 4 56.1.3 直接插入排序直接插入排序

7、適用例子：0 1 2 3 4 5 temp160 1 2 3 4 5 temp080 1 2 3 4 5完成6.1.3 直接插入排序直接插入排序 算法實(shí)現(xiàn)：void InsertSort int r , int n / 假設(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ù)和記錄挪動(dòng)次數(shù)與記錄關(guān)鍵字的初始陳列

8、有關(guān)。最好情況下, 排序前記錄已按關(guān)鍵字從小到大有序, 每趟只需與前面有序記錄序列的最后一個(gè)記錄比較1次, 挪動(dòng)2次記錄, 總的關(guān)鍵字比較次數(shù)為 n-1, 記錄挪動(dòng)次數(shù)為 2n-1在平均情況下的關(guān)鍵字比較次數(shù)和記錄挪動(dòng)次數(shù)約為 n2/4。直接插入排序是一種穩(wěn)定的排序方法直接插入排序最大的優(yōu)點(diǎn)是簡單，在記錄數(shù)較少時(shí)，是比較好的方法6.1.4 希爾排序希爾排序 希爾排序又稱減少增量排序 是1959年由D.L.Shell提出來的 算法描畫 先取定一個(gè)小于n的整數(shù)d作為第一個(gè)增量，把表的全部記錄分成d組 一切間隔 為d1的倍數(shù)的記錄放在同一組中，在各組內(nèi)進(jìn)展直接插入排序 然后取第二個(gè)增量d2d1 反復(fù)

9、上述的分組和排序，直至增量d1，即一切記錄放在同一組中進(jìn)展直接插入排序?yàn)橹埂?6.1.4 希爾排序希爾排序 算法特點(diǎn) 先取定一個(gè)小于n的整數(shù)d作為第一個(gè)增量，把表的全部記錄分成d組 一切間隔 為d1的倍數(shù)的記錄放在同一組中，在各組內(nèi)進(jìn)展直接插入排序 然后取第二個(gè)增量d2d1 反復(fù)上述的分組和排序，直至增量d1，即一切記錄放在同一組中進(jìn)展直接插入排序?yàn)橹埂?6.1.4 希爾排序希爾排序 運(yùn)用實(shí)例 先取定一個(gè)小于n的整數(shù)d作為第一個(gè)增量，把表的全部記錄分成d組 一切間隔 為d1的倍數(shù)的記錄放在同一組中，在各組內(nèi)進(jìn)展直接插入排序 然后取第二個(gè)增量d2d1 反復(fù)上述的分組和排序，直至增量d1，即一切記

10、錄放在同一組中進(jìn)展直接插入排序?yàn)橹埂?6.1.4 希爾排序希爾排序 希爾排序又稱減少增量排序 是1959年由D.L.Shell提出來的 算法描畫 首先取一個(gè)整數(shù) gap n待排序記錄數(shù) 作為間隔, 將全部記錄分為 gap 個(gè)子序列, 一切間隔 為 gap 的記錄放在同一個(gè)子序列中 在每一個(gè)子序列中分別施行直接插入排序。 然后減少間隔 gap, 例如取 gap = gap/2 反復(fù)上述的子序列劃分和排序任務(wù)，直到最后取gap = 1, 將一切記錄放在同一個(gè)序列中排序?yàn)橹埂?.1.4 希爾排序希爾排序 運(yùn)用實(shí)例 待排序的一組記錄的初始陳列為：21, 25, 49, 25*, 16, 080 1 2

11、 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 希爾排序希爾排序 算法分析 開場(chǎng)時(shí) gap 的值較大, 子序列中的記錄較少, 排序速度較快 隨著排序進(jìn)展, gap 值逐漸變小, 子序列中記錄個(gè)數(shù)逐漸變多,由于前面大多數(shù)記錄已根本有序, 所以排序速度依然很快 Gap的取法有多種。 shell 提出取 gap = n/2，gap = gap/2，直到gap = 1。6.1.5 選擇排序選擇排序 排序過程：排序過程： 首先經(jīng)過首先經(jīng)過n-1次比較，從次比較，從n個(gè)數(shù)中找出最小的，個(gè)數(shù)中找出最小的， 將它將它與第一個(gè)數(shù)與第一

12、個(gè)數(shù) 交換交換第一趟選擇排序，結(jié)果最小的數(shù)被安排在第第一趟選擇排序，結(jié)果最小的數(shù)被安排在第一個(gè)元素位置上一個(gè)元素位置上 再經(jīng)過再經(jīng)過n-2次比較，從剩余的次比較，從剩余的n-1個(gè)數(shù)中找出關(guān)鍵字個(gè)數(shù)中找出關(guān)鍵字次小的記錄，次小的記錄， 將它與第二個(gè)數(shù)交換將它與第二個(gè)數(shù)交換第二趟選擇排序第二趟選擇排序 反復(fù)上述過程，共經(jīng)過反復(fù)上述過程，共經(jīng)過n-1趟排序后，排序終了趟排序后，排序終了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 7

13、6 49 38 三趟： 13 27 38 97 76 49 65 四趟： 13 27 38 49 76 97 65 五趟： 13 27 38 49 65 97 76 六趟： 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最小者最小者 25*無交換無交換最小者最小者 25無交換無交換各趟排序后的結(jié)果各趟排序后的結(jié)果6.1.5 選擇排序選擇排序 算法實(shí)例：算法實(shí)例：0 1 2 3 4 5i =2時(shí)選擇排序的過程時(shí)選擇排序的過程i k

14、 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 個(gè)數(shù)給a1 到 anfor i=1 to n-1for j=i+1 to najak真假k=j輸出a1 到 ank=iaiaki != k真假#include main int a11,i,j,k,x; printfInput 10 numbers:n; fori=1;i11;i+ scanf%d,&ai; printfn; fori=1;i10;i+ k=i; forj=i+1;j=10;j+ ifajak k=j; ifi!=k x=ai; ai=ak; ak=x; printfThe sorted numbers:n; fori=1;i11;i+printf%d ,ai;階段小節(jié)階段小節(jié) 幾種常見的排序算法 冒泡排序的特點(diǎn) 快速排序的特點(diǎn)，一趟排序的子過程本章總結(jié)本章總結(jié)數(shù)據(jù)構(gòu)造與算法初步數(shù)據(jù)構(gòu)造與算法初步常見的排序算法重點(diǎn)講述冒泡排序和快速排序的特，同重點(diǎn)講述冒泡排序和快速排序的