《數(shù)據(jù)結(jié)構(gòu)與算法》第十章內(nèi)部排序分析.ppt

1、第十章 內(nèi)部排序,10.1 概述 10.2 插入排序 10.3 快速排序 10.4 選擇排序 10.5 歸并排序 10.6 基數(shù)排序 10.7 各種排序方法比較,101概述,一、排序的定義 假設(shè)有n個(gè)記錄的序列為：R1，R2，,Rn 其對(duì)應(yīng)的關(guān)鍵字為K1，K2，,Kn 需要確定1，2，,n的一種排列P1，P2，,Pn 使：Kp1K p2K p n 則R p1，R p2，,R pn為一個(gè)按關(guān)鍵字有序的序列。其中，Ki可以是記錄Ri的主關(guān)鍵字、次關(guān)鍵字或若干數(shù)據(jù)項(xiàng)的組合。,二、排序方法的穩(wěn)定性 若Ki=Kj,(1ijn),且排序前，Ri在Rj前面， 若排序后，Ri仍在Rj前面 則稱該排序算法是穩(wěn)定

2、的，否則是不穩(wěn)定的。,三、排序分類 根據(jù)待排序的記錄的數(shù)量劃分： 內(nèi)部排序： 待排序的記錄存放在計(jì)算機(jī)的內(nèi)存中的排序過(guò)程 外部排序： 待排序的記錄數(shù)量很大，內(nèi)存一次放不下全部記錄，在排序過(guò)程中還需訪問(wèn)外存的排序過(guò)程。,四、內(nèi)部排序方法 插入排序 交換排序 選擇排序 歸并排序 基數(shù)排序,五、待排序記錄的存儲(chǔ)方式 存放在地址連續(xù)的一組存儲(chǔ)單元-約定 存放在靜態(tài)鏈表 存放在地址連續(xù)的一組存儲(chǔ)單元，另設(shè)一組索引指針,#define MAXSIZE 20 /一個(gè)用作示例的小順序表的最大長(zhǎng)度 typedef int KeyType; /定義關(guān)鍵字類型為整數(shù)類型 typedef struct KeyType

3、 key; /關(guān)鍵字 InfoType otherinfo; /其它數(shù)據(jù)項(xiàng) RedType; /記錄類型 typedef struct RedType rMAXSIZE; /r0賦閑或用作哨兵單元 int length; /順序表長(zhǎng)度 SqList;,102插入排序insert sorting,一、直接插入排序 方法：將一個(gè)記錄插入已排好序的有序表中，得到一個(gè)新的記錄數(shù)增加1的有序表 （1）把序列(R(K1)看成是一個(gè)有序的子序列 把R(K2)插入到該序列中,使插入后序列 (R(K1),R(K2)有序 （2）把R(K3)插入到(R(K1),R(K2)中， 使插入后有序 （3）重復(fù)（2），直到插

4、入R(Kn)為止。,插入排序動(dòng)畫,12,34,32,29,64,45,34,78,45，34，78，12，34，32，29，64,45 34 45 34 45 78 12 34 45 78 12 34 34 45 78 12 32 34 34 45 78 12 29 32 34 34 45 78 12 29 32 34 34 45 64 78,void InsertSort(SqList /插入到正確位置 /InsertSort,算法分析,穩(wěn)定 空間代價(jià)：O(n) 時(shí)間代價(jià)： 最佳情況：n-1 次比較，O(n) 最差情況： O(n2) 比較次數(shù)為 平均情況：O(n2),例：在序列13，27，3

5、5，48，65，72中插入20或60,二、折半插入排序Binary Insertsort 用折半查找的方法找到插入位置,void BInsertSort(SqList /插入到正確位置 /BInsertSort,三、2-路插入排序 在折半查找的基礎(chǔ)上，減少排序過(guò)程中移動(dòng)的記錄次數(shù)。增加n個(gè)記錄的輔助空間： RedType dMAXSIZE+1; d1=L.r1; 把d1看成使排好序后序列的中間元素, d作為循環(huán)向量使用 然后把L.r2,L.r3,依次插入到d1之前(=d1) 另用指針first、final分別指向 排序后第一個(gè)記錄和最后一個(gè)記錄所在的位置。,例：key:49，38，65，97，

6、76，13，27，49,排序過(guò)程,四、希爾排序（縮小增量排序Shell Sort）,思想： 先將序列轉(zhuǎn)化為若干小序列，在這些小序列內(nèi)進(jìn)行插入排序 逐漸增加小序列的規(guī)模，而減少小序列個(gè)數(shù)，使得待排序序列逐漸處于更有序的狀態(tài) 最后對(duì)整個(gè)序列進(jìn)行一趟直接插入排序,直接插入排序的兩個(gè)特點(diǎn)： 在最好情況下時(shí)間代價(jià)為 O(n) 對(duì)于短序列，直接插入排序比較有效,按增量序列將整個(gè)待排記錄分割成若干個(gè)序列，分別進(jìn)行直接插入排序。等整個(gè)序列基本有序后，再對(duì)全體記錄進(jìn)行一次直接插入排序。 基本有序：序列中滿足以下特性的記錄較少,方法：,Shell排序動(dòng)畫,12,34,32,29,64,45,34,78,12,34

7、,32,29,64,45,34,78,12,34,32,29,64,45,34,78,12,34,32,29,64,45,34,78,12,34,32,29,64,45,34,78,增量序列為：5，3，1,49 38 65 97 76 13 27 49,13 27 49 97 76 49 38 65,13 27 49 97 76 49 38 65,13 27 49 38 65 49 97 76,13 27 38 49 49 65 76 97,void ShellInsert(SqList /插入 /ShellInsert,void ShellSort(SqList /一趟增量為daltk的插入

8、排序 /ShellSort,不穩(wěn)定 空間代價(jià)：O(n) 時(shí)間代價(jià) 增量序列不合適時(shí)，O(n2) 選擇適當(dāng)?shù)脑隽啃蛄?可以使得時(shí)間代價(jià)接近 O(n) Hibbard 增量序列2k -1，2k-1 -1，7，3，1 Hibbard 增量序列的 Shell 排序的效率可以達(dá)到 O(n3/2) 呈 2p3q 形式的一系列整數(shù)：1, 2, 3, 4, 6, 8, 9, 12 時(shí)間代價(jià)為O(n log2n),算法分析,103快速排序 一、起泡排序Bubble Sort,算法思想: 依次比較相鄰的記錄，如果不滿足排序要求，就交換相鄰記錄，直到所有的記錄都已經(jīng)排好序 檢查每次冒泡過(guò)程中是否發(fā)生過(guò)交換，如果沒(méi)有

9、，則表明整個(gè)數(shù)組已經(jīng)排好序了，排序結(jié)束，避免不必要的比較,void BubbleSort(SqList ,共進(jìn)行n-1趟排序， 共進(jìn)行n(n-1)/2次比較 T(n)=O(n2),算法分析,穩(wěn)定 空間代價(jià)：O(n) 時(shí)間代價(jià)： 比較次數(shù) 最少：O(n) 最多：,交換次數(shù)最多為 O(n2)，最少為 0，平均為 O(n2) 最壞，平均時(shí)間代價(jià)均為 O(n2) 最好時(shí)間代價(jià)為 O(n),二、快速排序Quick Sort,基本思想： 通過(guò)一趟排序?qū)⒋判蛴涗浄殖瑟?dú)立的兩部分， 其中一部分記錄的關(guān)鍵字均小于另一部分記錄 的關(guān)鍵字，然后分別對(duì)這兩部分進(jìn)行遞歸排序,一趟排序： 任意選取一個(gè)記錄作為樞軸（支點(diǎn)

10、）pivot, 將所有關(guān)鍵字小于它的記錄排在它的前面, 將所有關(guān)鍵字大于它的記錄排在它的后面。即以樞軸記錄為分界線，使原序列L.rs,L.rs+1,L.rt分成兩個(gè)子序列： L.rs,L.rs+1,L.ri-1和 L.ri+1,L.ri+2,L.rt 樞軸記錄在位置i,49 38 65 97 76 13 27 49,27 38 65 97 76 13 49 49,27 38 49 97 76 13 65 49,27 38 13 97 76 49 65 49,27 38 13 49 76 97 65 49,27 38 13,76 97 65 49,具體實(shí)現(xiàn)： low=s; high=t; piv

11、otkey=L.rlow.key; (1)從high開始往前找第一個(gè)關(guān)鍵字小于pivotkey的記錄，與樞軸記錄交換 (2)從low開始往后找第一個(gè)關(guān)鍵字大于pivotkey的記錄，與樞軸記錄交換 (3)重復(fù)（1）（2）直到low=high為止 此時(shí)樞軸記錄所在的位置i=low=high,27 38 13 49 76 97 65 49,13 27 38,49 65 76 97,int partition(SqList /返回樞軸所在的位置 /Partition,int partition(SqList /返回樞軸所在的位置 /Partition,void Qsort(SqList /對(duì)高子表遞

12、歸排序 /Qsort,void QuickSort(SqList /QuickSort,樞軸記錄的選擇,盡可能使兩部分長(zhǎng)度相等 選擇策略： 選擇最左/右/中間位置記錄 隨機(jī)選擇 選擇平均值,算法分析,最差情況： 時(shí)間代價(jià)：O(n2) 空間代價(jià)：O(n) 最佳情況： 時(shí)間代價(jià)：O(nlog n) 空間代價(jià)：O(log n) 平均情況： 時(shí)間代價(jià)：O(nlog n) 空間代價(jià)：O(log n),T(n)=O(nlog2n),12,34,32,29,64,45,34,78,104選擇排序 一、簡(jiǎn)單選擇排序Select Sort,void SelectSort(SqList /與第i記錄交換 ,int

13、 SelectMinKey(SqList L, int k) /在L.rk.L.length中選擇key最小的記錄并返回它的位置 min=L.rk.key; minp=k; for(i=k+1; i=L.length; i+) if(L.ri.keymin) min=L.ri.key; minp=i; return minp; ,不穩(wěn)定 空間代價(jià)：O(n) 時(shí)間代價(jià) 共進(jìn)行n-1趟排序 比較次數(shù)：O(n2) 交換次數(shù)：n-1 總時(shí)間代價(jià)：O(n2),算法分析,二、樹形選擇排序 （1）對(duì)n個(gè)記錄的關(guān)鍵字兩兩比較， 共進(jìn)行n/2次，最后找出最小記錄 此過(guò)程可以用有n個(gè)葉子的完全二叉樹表示 （2）將

14、葉子結(jié)點(diǎn)中最小關(guān)鍵字改為MAXINT， 然后該葉子與其左/右兄弟關(guān)鍵字比較 依次修改從葉子到根的路徑上各結(jié)點(diǎn)的關(guān)鍵字值 則根結(jié)點(diǎn)為次小記錄 （3）重復(fù)（2），直到葉子結(jié)點(diǎn)均為MAXINT為止。,a0,a1,a2,a3,a4,a5,a6,a7,若用一個(gè)一維數(shù)組存放滿足此關(guān)系的序列，把這個(gè)一維數(shù)組看成是一棵完全二叉樹，則堆對(duì)應(yīng)的完全二叉樹中所有非終端結(jié)點(diǎn)的值均大于或均小于其左右孩子的值。,大頂堆/大根堆,堆排序方法： （1）由一個(gè)無(wú)序的序列建成一個(gè)堆 （2）輸出堆頂?shù)淖钚≈?（3）剩余的元素建成一個(gè)新的堆 （4）重復(fù)（2）（3）,49 38 65 97 76 13 27 49,輸出13后,用序列中

15、最后一個(gè)記錄代替根結(jié)點(diǎn),篩選為,堆頂元素與它的左右子樹根結(jié)點(diǎn)比較 若右子樹根左子樹根堆頂 根結(jié)點(diǎn)與右子樹根交換 若左子樹根右子樹根堆頂 根結(jié)點(diǎn)與左子樹根交換 這個(gè)調(diào)整過(guò)程稱為篩選,對(duì)一個(gè)無(wú)序序列建立堆也是篩選過(guò)程,篩選從n/2個(gè)記錄開始。,49 38 65 97 76 13 27 49,建大頂堆，排序結(jié)果為從小到大,typedef SqList HeapType; void HeapAdjust(HeapType /rc應(yīng)插入在位置s上 /HeapAdjust,void HeapSort(HeapType /將H.r1.i-1重新調(diào)整為大頂堆 /HeapSort,算法分析,建堆：O(n) 刪除

16、堆頂: O(log n ) 一次建堆，n 次刪除堆頂 總時(shí)間代價(jià)為 O(nlog n) 空間代價(jià)為 O(n),T(n)=O(nlog2n),105歸并排序 Merge Sort 將兩個(gè)以上的有序序列合并成一個(gè)新的有序序列,2路歸并： 把初始含有n個(gè)記錄的序列看成n個(gè)長(zhǎng)度為1的有序子序列,采用兩兩合并的方法最終合并成一個(gè)序列,void Merge(RedType SR , RedType /將剩余的SRj.n復(fù)制到TR /Merge,void MSort(RedType SR , RedType /將TR2s.m和TR2m+1.t歸并到TR1s.t /Msort,void MergeSort(S

17、qList /MergeSort,算法分析,穩(wěn)定 空間代價(jià)：O(n) 時(shí)間代價(jià)： T(n)=2T(n/2)+cn T(1) = 1 歸并排序總時(shí)間代價(jià)為O(nlog n) 任何情況下都是,106基數(shù)排序Radix Sort 不通過(guò)關(guān)鍵字之間的比較進(jìn)行排序 一、多關(guān)鍵字排序,最高位優(yōu)先法MSD： 先按關(guān)鍵字K0排序， 將序列分成若干個(gè)子序列 每個(gè)子序列記錄的K0均相等 然后在每個(gè)子序列中按K1排序 按K1值把子序列分成更小的子序列 直到最后按Kd-1排序后， 整個(gè)序列有序,(1,1),(2,4),(1,3),(3,2),(4,4),(2,3),(4,3),(3,4),(1,1),(1,3),(2

18、,4),(2,3),(3,2),(3,4),(4,4),(4,3),(1,1),(1,3),(2,3),(2,4),(3,2),(3,4),(4,3),(4,4),最低位優(yōu)先法LSD： 根據(jù)最次關(guān)鍵字Kd-1起對(duì)記錄排序 再根據(jù)Kd-2對(duì)記錄排序 。 根據(jù)K0對(duì)記錄排序后， 整個(gè)序列有序,(1,1),(2,4),(1,3),(3,2),(4,4),(2,3),(4,3),(3,4),(1,1),(3,2),(1,3),(2,3),(4,3),(2,4),(4,4),(3,4),(1,1),(1,3),(2,3),(2,4),(3,2),(3,4),(4,3),(4,4),二、鏈?zhǔn)交鶖?shù)排序 用分配和收集兩種操作對(duì)單關(guān)鍵字進(jìn)行排序 某些單關(guān)鍵字可以看成是若干個(gè)關(guān)鍵字復(fù)合而成,如多位數(shù)可以看成是由多個(gè)數(shù)