《數(shù)據(jù)結(jié)構(gòu)及算法排序課件.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)及算法排序課件.ppt（116頁(yè)珍藏版）》請(qǐng)?jiān)趨R文網(wǎng)上搜索。

1、第八章第八章第八章第八章 排序技術(shù)排序技術(shù)排序技術(shù)排序技術(shù)本章的基本內(nèi)容是：本章的基本內(nèi)容是：排序的基本概念排序的基本概念插入排序插入排序交換排序交換排序選擇排序選擇排序歸并排序歸并排序 8.18.18.18.1概概概概 述述述述 排排序序：將將一一組組“無(wú)無(wú)序序”的的記記錄錄序序列列,調(diào)調(diào)整整為為按按關(guān)關(guān)鍵鍵字字“有有序序”的記錄序列的記錄序列.學(xué)號(hào)學(xué)號(hào)姓名姓名高數(shù)高數(shù)英語(yǔ)英語(yǔ)思想品德思想品德0002王王 軍軍85880001李李 明明64920003湯曉影湯曉影85866872781.1.排序的基本概念排序的基本概念排序的基本概念排序的基本概念排排序序：給給定定一一組組記記錄錄的的集集合合

2、r1,r2,rn，其其相相應(yīng)應(yīng)的的關(guān)關(guān)鍵鍵碼碼分分別別為為k1,k2,kn，排排序序是是將將這這些些記記錄錄排排列列成成順順序序?yàn)闉閞s1,rs2,rsn的的一一個(gè)個(gè)序序列列，使使得得相相應(yīng)應(yīng)的的關(guān)關(guān)鍵鍵碼碼滿滿足足非非遞遞減減關(guān)關(guān)系系ks1ks2ksn（稱稱為為升升序序）或或非非遞遞增增關(guān)關(guān)系系ks1ks2ksn（稱為稱為降序降序）。）。1.1.排序的基本概念排序的基本概念排序的基本概念排序的基本概念學(xué)號(hào)學(xué)號(hào)姓名姓名高數(shù)高數(shù)英語(yǔ)英語(yǔ)0002李李 明明640001王王 軍軍850003湯曉影湯曉影85726878學(xué)號(hào)學(xué)號(hào)姓名姓名高數(shù)高數(shù)英語(yǔ)英語(yǔ)0001王王 軍軍850002李李 明明64000

3、3湯曉影湯曉影856872788.18.18.18.1概概概概 述述述述 假定在待排序的記錄集中，存在假定在待排序的記錄集中，存在多多個(gè)具有相同鍵值個(gè)具有相同鍵值的記錄，若經(jīng)過(guò)排序，這些記錄的的記錄，若經(jīng)過(guò)排序，這些記錄的相相對(duì)次序?qū)Υ涡蛉匀槐３植蛔?，即在原序列中，仍然保持不變，即在原序列中，ki=kj且且ri在在rj之之前，前，而在排序后的序列中，而在排序后的序列中，ri一定在一定在rj之前之前，則稱這種，則稱這種排序算法是排序算法是穩(wěn)定的穩(wěn)定的；否則稱為；否則稱為不穩(wěn)定的不穩(wěn)定的。學(xué)號(hào)學(xué)號(hào)姓名姓名高數(shù)高數(shù)英語(yǔ)英語(yǔ)思想品德思想品德0001王王 軍軍85880002李李 明明64920003湯

4、曉影湯曉影8586687278排序算法的穩(wěn)定性：排序算法的穩(wěn)定性：8.18.18.18.1概概概概 述述述述 1.1.排序的基本概念排序的基本概念排序的基本概念排序的基本概念 待排序序列中的記錄已按關(guān)鍵碼待排序序列中的記錄已按關(guān)鍵碼排好序排好序。待排序序列中記錄的排列順序與排好待排序序列中記錄的排列順序與排好序的順序序的順序正好相反正好相反。學(xué)號(hào)學(xué)號(hào)姓名姓名高數(shù)高數(shù)英語(yǔ)英語(yǔ)思想品德思想品德0001王王 軍軍85880002李李 明明64920003湯曉影湯曉影85866872788.18.18.18.1概概概概 述述述述 1.1.排序的基本概念排序的基本概念排序的基本概念排序的基本概念正序：正

5、序：逆序（反序）：逆序（反序）：排序的分類排序的分類 在排序的整個(gè)過(guò)程中，待排序的所有記錄在排序的整個(gè)過(guò)程中，待排序的所有記錄全部被放置在內(nèi)存中全部被放置在內(nèi)存中,不需要訪問(wèn)外存不需要訪問(wèn)外存 由于待排序的記錄個(gè)數(shù)太多，由于待排序的記錄個(gè)數(shù)太多，不能同時(shí)放不能同時(shí)放置在內(nèi)存置在內(nèi)存，而需要將一部分記錄放置在內(nèi)存，另一部，而需要將一部分記錄放置在內(nèi)存，另一部分記錄放置在外存上，整個(gè)排序過(guò)程需要在分記錄放置在外存上，整個(gè)排序過(guò)程需要在內(nèi)外存之內(nèi)外存之間多次交換數(shù)據(jù)間多次交換數(shù)據(jù)才能得到排序的結(jié)果。才能得到排序的結(jié)果。8.18.18.18.1概概概概 述述述述 1.1.排序的基本概念排序的基本概念排

6、序的基本概念排序的基本概念1.1.內(nèi)排序：內(nèi)排序：2.2.外排序：外排序：2.2.內(nèi)排序算法內(nèi)排序算法內(nèi)排序算法內(nèi)排序算法 1.插入排序插入排序 2.交換排序交換排序 3.選擇排序選擇排序 4.歸并排序歸并排序直接插入排序直接插入排序希爾排序希爾排序冒泡排序冒泡排序快速排序快速排序簡(jiǎn)單選擇排序簡(jiǎn)單選擇排序堆排序堆排序8.18.18.18.1概概概概 述述述述 排排序序基基本本過(guò)過(guò)程程:是是一一個(gè)個(gè)逐逐步步擴(kuò)擴(kuò)大大記記錄錄的的有有序序序序列列長(zhǎng)長(zhǎng)度度的過(guò)程的過(guò)程3.3.排序的基本過(guò)程排序的基本過(guò)程排序的基本過(guò)程排序的基本過(guò)程有序序列區(qū)無(wú)序序列區(qū)有序序列區(qū)無(wú)序序列區(qū)一趟排序一趟排序:將無(wú)序序列區(qū)里

7、一個(gè)或幾個(gè)記錄合并到有序序列的過(guò)程為一趟排序，有序序列長(zhǎng)度增加1個(gè)或幾個(gè)8.18.18.18.1概概概概 述述述述 4.4.排序算法的存儲(chǔ)結(jié)構(gòu)排序算法的存儲(chǔ)結(jié)構(gòu)排序算法的存儲(chǔ)結(jié)構(gòu)排序算法的存儲(chǔ)結(jié)構(gòu)從操作角度看，排序是從操作角度看，排序是線性結(jié)構(gòu)線性結(jié)構(gòu)的一種操作，待排序的一種操作，待排序記錄可以用記錄可以用順序順序存儲(chǔ)結(jié)構(gòu)或存儲(chǔ)結(jié)構(gòu)或鏈接鏈接存儲(chǔ)結(jié)構(gòu)存儲(chǔ)。存儲(chǔ)結(jié)構(gòu)存儲(chǔ)。假定假定2：將待排序的記錄序列將待排序的記錄序列排序?yàn)榕判驗(yàn)樯蛏蛐蛄?。序列。rn+1 假定假定1 1：待排序記錄：待排序記錄采用采用順序順序存儲(chǔ)結(jié)構(gòu)，關(guān)鍵碼為存儲(chǔ)結(jié)構(gòu)，關(guān)鍵碼為整整型型，且記錄只有關(guān)鍵碼，且記錄只有關(guān)鍵碼一個(gè)

8、一個(gè)數(shù)據(jù)項(xiàng)。數(shù)據(jù)項(xiàng)。8.18.18.18.1概概概概 述述述述 10 15 24 6 12 35 40 980 1 2 3 4 5 6 7 8內(nèi)排序算法內(nèi)排序算法內(nèi)排序算法內(nèi)排序算法 1.插入排序插入排序 2.交換排序交換排序 3.選擇排序選擇排序 4.歸并排序歸并排序直接插入排序直接插入排序希爾排序希爾排序冒泡排序冒泡排序快速排序快速排序簡(jiǎn)單選擇排序簡(jiǎn)單選擇排序堆排序堆排序8.18.18.18.1概概概概 述述述述 8.28.28.28.2插入排序插入排序插入排序插入排序插入排序的主要操作是插入排序的主要操作是插入插入，其基本思想是：，其基本思想是：每次將一個(gè)每次將一個(gè)待排序的記錄待排序的記

9、錄按其關(guān)鍵碼的大小插按其關(guān)鍵碼的大小插入到一個(gè)已經(jīng)排好序的入到一個(gè)已經(jīng)排好序的有序序列有序序列中，中，直到直到全部全部記錄排好序?yàn)橹埂Ｓ涗浥藕眯驗(yàn)橹?。舉例:有序序列 2,待排序記錄 3,6,11）直接插入排序）直接插入排序2）希爾排序）希爾排序基本思想基本思想：在插入第：在插入第 i（i1）個(gè)記錄時(shí)，前面的）個(gè)記錄時(shí)，前面的 i-1個(gè)記錄已經(jīng)排好序。個(gè)記錄已經(jīng)排好序。8.2.18.2.1直接插入排序直接插入排序直接插入排序直接插入排序有序序列有序序列無(wú)序序列無(wú)序序列r r1r r2r ri-1r rir rnr ri+1r r1r r2r ri-1r rir rnr ri+1有序序列有序序列無(wú)

10、序序列無(wú)序序列8.28.28.28.2插入排序插入排序插入排序插入排序直接插入排序過(guò)程示例直接插入排序過(guò)程示例直接插入排序過(guò)程示例直接插入排序過(guò)程示例 r 0 1 2 3 4 5 62121181825252222101025*25*2121第一趟18182222101025*25*252525252222212125252222212110102525*25252222212110102525*252522222121181810101818101025*25*第二趟1818第四趟18182525*第三趟第五趟算法穩(wěn)定嗎？2121算法思想？i從第2個(gè)數(shù)到第n個(gè)數(shù) 將第i個(gè)數(shù)插入到有序序列中的

11、合理位置8.28.28.28.2插入排序插入排序插入排序插入排序共多少趟？對(duì)于對(duì)于riri，如何查找它的，如何查找它的插入位置插入位置?如何如何實(shí)現(xiàn)插入實(shí)現(xiàn)插入？直接插入排序直接插入排序直接插入排序直接插入排序需解決的關(guān)鍵問(wèn)題需解決的關(guān)鍵問(wèn)題?無(wú)序序列無(wú)序序列202025252121181826261)將ri暫存在r02)j=i-1；/從第i-1記錄開(kāi)始查找3)當(dāng)rjr0時(shí)，循環(huán)做 rj后移一個(gè)位置,j-4)rj+1=r0 /將r0插入到位置j+12222 0 1 2 3 4 5 2121ij2525j2222j21218.28.28.28.2插入排序插入排序插入排序插入排序直接插入排序直接插

12、入排序直接插入排序直接插入排序無(wú)序序列無(wú)序序列202025251010181825252222 0 1 2 3 4 5 1010ij2525222220201010jr0的作用的作用?暫存單元暫存單元,監(jiān)視哨監(jiān)視哨 對(duì)于對(duì)于riri，如何查找它的，如何查找它的插入位置插入位置?如何如何實(shí)現(xiàn)插入實(shí)現(xiàn)插入？需解決的關(guān)鍵問(wèn)題需解決的關(guān)鍵問(wèn)題?1)將ri暫存在r02)j=i-1；/從第i-1記錄開(kāi)始查找3)當(dāng)rjr0時(shí)，循環(huán)做 rj后移一個(gè)位置,j-4)rj+1=r0 /將r0插入到位置j+1jj8.28.28.28.2插入排序插入排序插入排序插入排序void insertSort(int r,int

13、 n)for(i=2;i=n;i+)r0=ri;for(j=i-1;r0r0時(shí)，循環(huán)做：時(shí)，循環(huán)做：rj后移一個(gè)位置后移一個(gè)位置,j-1.4 rj+1=r08.28.28.28.2插入排序插入排序插入排序插入排序直接插入排序過(guò)程示例直接插入排序過(guò)程示例直接插入排序過(guò)程示例直接插入排序過(guò)程示例 r 0 1 2 3 4 5 62121181825252222101025*25*212121212525i=218182222101025*25*2525i=318182222101025*25*22222525222221211010252522222121101025252525*252522222

14、12110102525*2525222221211818101018181818101025*25*i=41818i=618182525*i=5252521218.28.28.28.2插入排序插入排序插入排序插入排序直接插入排序練習(xí)直接插入排序練習(xí)直接插入排序練習(xí)直接插入排序練習(xí) 12 5 9 20 6 31 248.28.28.28.2插入排序插入排序插入排序插入排序直接插入排序練習(xí)直接插入排序練習(xí)直接插入排序練習(xí)直接插入排序練習(xí) 12 5 9 20 6 31 24初始序列 5 12 9 20 6 31 24第一趟 5 9 12 20 6 31 24第二趟 5 9 12 20 6 31 24

15、第三趟 5 6 9 12 20 31 24第四趟第五趟 5 6 9 12 20 31 24第六趟 5 6 9 12 20 24 318.28.28.28.2插入排序插入排序插入排序插入排序1.基本操作基本操作。內(nèi)排序在排序過(guò)程中的基本操作：。內(nèi)排序在排序過(guò)程中的基本操作：比較比較：關(guān)鍵碼之間的比較；：關(guān)鍵碼之間的比較；移動(dòng)移動(dòng)：記錄從一個(gè)位置移動(dòng)到另一個(gè)位置。：記錄從一個(gè)位置移動(dòng)到另一個(gè)位置。2.輔助存儲(chǔ)空間輔助存儲(chǔ)空間。輔助存儲(chǔ)空間是指在數(shù)據(jù)規(guī)模一定的條件下，除了存輔助存儲(chǔ)空間是指在數(shù)據(jù)規(guī)模一定的條件下，除了存放待排序記錄占用的存儲(chǔ)空間之外，執(zhí)行算法所需要放待排序記錄占用的存儲(chǔ)空間之外，執(zhí)行

16、算法所需要的其他存儲(chǔ)空間。的其他存儲(chǔ)空間。3.算法本身的復(fù)雜程度算法本身的復(fù)雜程度。排序排序排序排序算法的性能算法的性能算法的性能算法的性能8.28.28.28.2插入排序插入排序插入排序插入排序直接插入排序算法性能分析直接插入排序算法性能分析直接插入排序算法性能分析直接插入排序算法性能分析最好情況下：最好情況下：1 12 23 34 45 5時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為O(n)。比較次數(shù)：比較次數(shù)：n-1移動(dòng)次數(shù)：移動(dòng)次數(shù)：2(n-1)1 12 23 34 45 52 21 12 23 34 45 53 31 12 23 34 45 54 41 12 23 34 45 55 5（正序）（正序）8.28.28.28.2插入排序插入排序插入排序插入排序直接插入排序算法性能分析直接插入排序算法性能分析直接插入排序算法性能分析直接插入排序算法性能分析最好最好情況下（正序）：情況下（正序）：比較次數(shù)：比較次數(shù)：n-1移動(dòng)次數(shù)：移動(dòng)次數(shù)：2(n-1)最壞最壞情況下（逆序）：情況下（逆序）：時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為O(n2)。5 54 43 32 21 14 45 53 32 21 14 43 34