數(shù)據(jù)結(jié)構(gòu)與算法內(nèi)部排序分析PPT課件

1、第1頁/共70頁第2頁/共70頁第3頁/共70頁第4頁/共70頁第5頁/共70頁6目錄頁張銘、鄒艷珍、劉楚雄、閆宏飛、郝丹數(shù)據(jù)結(jié)構(gòu)與算法插入排序動(dòng)畫 1234322964453478第6頁/共70頁45，34，78，12，34，32，29，64 45 45 34 45 34 45 34 45 78 34 45 78 12 34 45 78 12 34 45 78 12 34 12 34 3434 45 78 45 78 12 32 34 12 32 34 3434 45 78 45 78 12 29 32 34 12 29 32 34 3434 45 78 45 78 12 29 32 34

2、34 45 64 78 12 29 32 34 34 45 64 78第7頁/共70頁第8頁/共70頁算法分析穩(wěn)定空間代價(jià)：O(n) 時(shí)間代價(jià)： 最佳情況：n-1 次比較，O(n) 最差情況： O(n2) 比較次數(shù)為 平均情況：O(n2) 第9頁/共70頁3565132748722060第10頁/共70頁第11頁/共70頁例：例：key:49，38，65，97，76，13，27，49,排序過程排序過程第12頁/共70頁49491firstfirstfinalfinal494938382finalfinalfirstfirst4949656538383finalfinalfirstfirst49

3、496565979738384finalfinalfirstfirst494965657676979738385finalfinalfirstfirst4949656576769797131338386finalfinalfirstfirst49496565767697971313272738387finalfinalfirstfirst494949496565767697971313272738388finalfinalfirstfirst第13頁/共70頁思想： 先將序列轉(zhuǎn)化為若干小序列，在這些小序列內(nèi)進(jìn)行插入排序 逐漸增加小序列的規(guī)模，而減少小序列個(gè)數(shù)，使得待排序序列逐漸處于更有序的狀態(tài)

4、 最后對整個(gè)序列進(jìn)行一趟直接插入排序直接插入排序的兩個(gè)特點(diǎn)：在最好情況下時(shí)間代價(jià)為 O(n)對于短序列，直接插入排序比較有效第14頁/共70頁.1keyjrLMAXkeyirLij 按增量序列將整個(gè)待排記錄分割成若干個(gè)序列，分別進(jìn)行直接插入排序。等整按增量序列將整個(gè)待排記錄分割成若干個(gè)序列，分別進(jìn)行直接插入排序。等整個(gè)序列基本有序后，再對全體記錄進(jìn)行一次直接插入排序。個(gè)序列基本有序后，再對全體記錄進(jìn)行一次直接插入排序。：序列中滿足以下特性的記錄較少：序列中滿足以下特性的記錄較少方法：方法：第15頁/共70頁16目錄頁張銘、鄒艷珍、劉楚雄、閆宏飛、郝丹數(shù)據(jù)結(jié)構(gòu)與算法Shell排序動(dòng)畫 12343

5、229644534781234322964453478123432296445347812343229644534781234322964453478第16頁/共70頁增量序列為：增量序列為：5 5，3 3，1 1第17頁/共70頁第18頁/共70頁void ShellSort(SqList &L, int dlta ,int t) /按增量序列按增量序列dlta0.t-1對順序表對順序表L作希爾排序作希爾排序 for(k=0; kt; + t) ShellInsert(L,dltak); /一趟增量為一趟增量為daltk的插入排序的插入排序/ShellSort第19頁/共70頁 不穩(wěn)

6、定 空間代價(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) 算法分析第20頁/共70頁算法思想:依次比較相鄰的記錄，如果不滿足排序要求，就交換相鄰記錄，直到所有的記錄都已經(jīng)排好序檢查每次冒泡過程中是否發(fā)生過交換，如果沒有，則表明整個(gè)數(shù)組已經(jīng)排好序了，排序結(jié)束，避免不必要的比較第21頁/共70

7、頁void BubbleSort(SqList &L) for(i=1;iL.length; i+) change=FALSE; for(j=1; jL.rj+1.key) change=TRUE; L.rjL.rj+1; if(!change) return; 共進(jìn)行共進(jìn)行n-1n-1趟排序，趟排序，共進(jìn)行共進(jìn)行n(n-1)/2n(n-1)/2次比較次比較T(n)=O(nT(n)=O(n2 2) )第22頁/共70頁算法分析 穩(wěn)定 空間代價(jià)：O(n) 時(shí)間代價(jià)： 比較次數(shù) 最少：O(n) 最多：交換次數(shù)最多為 O(n2)，最少為 0，平均為 O(n2)最壞，平均時(shí)間代價(jià)均為 O(n2

8、)最好時(shí)間代價(jià)為 O(n)第23頁/共70頁基本思想：基本思想： 通過一趟排序?qū)⒋判蛴涗浄殖瑟?dú)立的兩部分，通過一趟排序?qū)⒋判蛴涗浄殖瑟?dú)立的兩部分， 其中一部分記錄的關(guān)鍵字均小于另一部分記錄其中一部分記錄的關(guān)鍵字均小于另一部分記錄 的關(guān)鍵字，然后分別對這兩部分進(jìn)行遞歸排序的關(guān)鍵字，然后分別對這兩部分進(jìn)行遞歸排序 第24頁/共70頁49 38 65 97 76 13 27 49i27 38 65 97 76 13 49 4927 38 49 97 76 13 65 49jiiijjijj27 38 13 97 76 49 65 49iji27 38 13 49 76 97 65 49ij27

9、38 13jj第25頁/共70頁27 38 13 49 76 97 65 49第26頁/共70頁第27頁/共70頁第28頁/共70頁第29頁/共70頁樞軸記錄的選擇盡可能使兩部分長度相等選擇策略： 選擇最左/右/中間位置記錄 隨機(jī)選擇 選擇平均值第30頁/共70頁算法分析最差情況： 時(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) 第31頁/共70頁102101)(2)()(2)()1(1)(nininiiTnnnTiTnninTiTnnnTT(n)=O(nlog

10、2n)第32頁/共70頁33目錄頁張銘、鄒艷珍、劉楚雄、閆宏飛、郝丹數(shù)據(jù)結(jié)構(gòu)與算法1234322964453478第33頁/共70頁第34頁/共70頁不穩(wěn)定 空間代價(jià)：O(n) 時(shí)間代價(jià) 共進(jìn)行n-1趟排序 比較次數(shù)：O(n2) 交換次數(shù)：n-1 總時(shí)間代價(jià)：O(n2) 算法分析算法分析第35頁/共70頁第36頁/共70頁a0a11621161663252121254925166395第37頁/共70頁第38頁/共70頁第39頁/共70頁第40頁/共70頁 若用一個(gè)一維數(shù)組存放滿足此關(guān)系的序列，若用一個(gè)一維數(shù)組存放滿足此關(guān)系的序列，把這個(gè)一維數(shù)組看成是一棵完全二叉樹，則把這個(gè)一維數(shù)組看成是一棵

11、完全二叉樹，則堆對應(yīng)的完全二叉樹中所有非終端結(jié)點(diǎn)的值堆對應(yīng)的完全二叉樹中所有非終端結(jié)點(diǎn)的值均大于或均小于其左右孩子的值。均大于或均小于其左右孩子的值。第41頁/共70頁大大頂頂堆堆/ /大大根根堆堆堆排序方法：堆排序方法：（1 1）由一個(gè)無序的序列建成一個(gè)堆）由一個(gè)無序的序列建成一個(gè)堆（2 2）輸出堆頂?shù)淖钚≈担┹敵龆秧數(shù)淖钚≈担? 3）剩余的元素建成一個(gè)新的堆）剩余的元素建成一個(gè)新的堆（4 4）重復(fù)（）重復(fù)（2 2）（）（3 3）093811962783小小頂頂堆堆/ /小小根根堆堆3085471224369153第42頁/共70頁49 38 65 97 76 13 27 49輸出輸出131

12、3后后, ,用用序列中最后一序列中最后一個(gè)記錄代替根個(gè)記錄代替根結(jié)點(diǎn)結(jié)點(diǎn)篩篩選選為為堆頂元素與它的左右子樹根結(jié)點(diǎn)比較堆頂元素與它的左右子樹根結(jié)點(diǎn)比較若右子樹根若右子樹根 左子樹根左子樹根 堆頂堆頂 根結(jié)點(diǎn)與右子樹根交換根結(jié)點(diǎn)與右子樹根交換若左子樹根若左子樹根 右子樹根右子樹根 堆頂堆頂 根結(jié)點(diǎn)與左子樹根交換根結(jié)點(diǎn)與左子樹根交換這個(gè)調(diào)整過程稱為這個(gè)調(diào)整過程稱為篩選篩選13384976972765499738497627654927384976496597第43頁/共70頁對一個(gè)無序序列建立堆也是篩選過程對一個(gè)無序序列建立堆也是篩選過程,篩選篩選從從n/2個(gè)記錄開始。個(gè)記錄開始。49 38 65

13、97 76 13 27 497627496538974913496538974997657649273813第44頁/共70頁499765764927381349386576492797134976654938279713第45頁/共70頁497665493827971349276549387697134965274938769713第46頁/共70頁496527493876971349132749387697651349274938769765第47頁/共70頁134927493876976549132749387697654949273813769765第48頁/共70頁494927381

14、376976549132738497697654938271349769765第49頁/共70頁494938382727131349497676979765654949272738381313494976769797656549491313383827274949767697976565建建大頂堆大頂堆，排序，排序結(jié)果為結(jié)果為從小到大從小到大第50頁/共70頁第51頁/共70頁第52頁/共70頁算法分析建堆：O(n) 刪除堆頂: O(log n ) 一次建堆，n 次刪除堆頂總時(shí)間代價(jià)為 O(nlog n) 空間代價(jià)為 O(n) T(n)=O(nlog2n)第53頁/共70頁10105 5歸并排

15、序歸并排序 Merge Sort 將兩個(gè)以上的有序序列合并成一個(gè)新的有序序列將兩個(gè)以上的有序序列合并成一個(gè)新的有序序列第54頁/共70頁第55頁/共70頁第56頁/共70頁第57頁/共70頁算法分析穩(wěn)定空間代價(jià)：O(n) 時(shí)間代價(jià)： T(n)=2T(n/2)+cn T(1) = 1 歸并排序總時(shí)間代價(jià)為O(nlog n) 任何情況下都是第58頁/共70頁10106 6基數(shù)排序基數(shù)排序Radix SortRadix Sort 不通過關(guān)鍵字之間的比較進(jìn)行排序不通過關(guān)鍵字之間的比較進(jìn)行排序 一、多關(guān)鍵字排序一、多關(guān)鍵字排序第59頁/共70頁(1,1),(2,4),(1,3),(3,2),(4,4),

16、(2,3),(4,3),(3,4)(1,1),(1,3),(2,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)第60頁/共70頁(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)第61頁/共70頁第62頁/共70頁614921485637738101215

17、530790306530790921101614485215637738 614738921485637101215530790306 第63頁/共70頁614921485637738101215530790306530790921101614485215306637738614738921485637101215530790306 第64頁/共70頁614921485637738101215530790306530790921101614485215306637738614738921485637101215530790306 第65頁/共70頁10107 7各種排序方法比較各種排序方法比較

18、 排序方法排序方法平均時(shí)間平均時(shí)間最壞情況最壞情況輔助存儲輔助存儲直接插入排序直接插入排序O(nO(n2 2) )O(nO(n2 2) )O(1)O(1)直接選擇排序直接選擇排序冒泡排序冒泡排序快速排序快速排序O(nlogn)O(nlogn)O(nO(n2 2) )O(logn)O(logn)堆排序堆排序O(nlogn)O(nlogn)O(nlogn)O(nlogn)O(1)O(1)歸并排序歸并排序O(nlogn)O(nlogn)O(nlogn)O(nlogn)O(n)O(n)基數(shù)排序基數(shù)排序O(d(n+rd)O(d(n+rd) O(d(n+rd)O(d(n+rd)O(rd)O(rd)第66頁/共70頁 排序方法 穩(wěn)定性 方法類別 直接插入排序 穩(wěn)定 插入 直接選擇排序 不穩(wěn)定 選擇 冒泡排序 穩(wěn)定 交換 快速排序 不穩(wěn)定 交換 堆排序 不穩(wěn)定 選擇 歸并排序 穩(wěn)定 合并 基數(shù)排序 穩(wěn)定 比較和移動(dòng) 希爾排序 不穩(wěn)定 插入第67頁/共70頁規(guī)模1010010K