參考第10章排序

1、2022/7/261第10章 內(nèi)部排序 排序的概念及種類(lèi) 插入排序的具體實(shí)現(xiàn)及算法分析 快速排序的具體實(shí)現(xiàn)及算法分析 選擇排序的具體實(shí)現(xiàn)及算法分析 歸并排序的具體實(shí)現(xiàn)及算法分析 各種內(nèi)部排序方法的比較討論2022/7/262本章導(dǎo)讀 排序是日常工作和軟件設(shè)計(jì)中常用的運(yùn)算之一。為了提高查詢(xún)速度需要將無(wú)序序列按照一定的順序組織成有序序列。由于需要排序的數(shù)據(jù)表的基本特性可能存在差異，使得排序方法也不同。如何合理地組織數(shù)據(jù)的邏輯順序，按照何種方式排出的序列最有效？這是本章要討論的主題。本章主要介紹排序的概念及幾種最常見(jiàn)的排序方法，討論其性能和特點(diǎn)，并在此基礎(chǔ)上進(jìn)一步討論各種方法的適用場(chǎng)合，以便在實(shí)際應(yīng)

2、用中能根據(jù)具體的問(wèn)題選擇合適的排序方法。 排序的應(yīng)用十分廣泛，電商推薦、路線導(dǎo)航、搜索排行、績(jī)效考核、檔案管理、圖書(shū)字典等等。10.1 概述2022/7/2632022/7/264排序分類(lèi) 增排序和減排序：如果排序的結(jié)果是按關(guān)鍵字從小到大的次序排列的，就是增排序，否則就是減排序。 穩(wěn)定排序和不穩(wěn)定排序：假設(shè)Ki=Kj（1in，1jn，ij），且在排序前的序列中Ri領(lǐng)先于Rj（即ij）。若在排序后的排序中Ri仍領(lǐng)先于Rj，即那些具有相同關(guān)鍵字的記錄，經(jīng)過(guò)排序后它們的相對(duì)次序仍然保持不變，則稱(chēng)這種排序方法是穩(wěn)定的；反之，若Rj領(lǐng)先于Ri，則稱(chēng)所用的方法是不穩(wěn)定的。 2022/7/265(3) 內(nèi)部

3、排序與外部排序：在排序中，若數(shù)據(jù)表中的所有記錄的排列過(guò)程都是在內(nèi)存中進(jìn)行的，稱(chēng)為內(nèi)部排序。由于待排序的記錄數(shù)量太多，在排序過(guò)程中不能同時(shí)把全部記錄放在內(nèi)存，需要不斷地通過(guò)在內(nèi)存和外存之間交換數(shù)據(jù)元素來(lái)完成整個(gè)排序的過(guò)程，稱(chēng)為外部排序。 在外部排序情況下，只有部分記錄進(jìn)入內(nèi)存，在內(nèi)存中進(jìn)行內(nèi)部排序，待排序完成后再交換到外部存儲(chǔ)器中加以保存。然后再將其它待排序的記錄調(diào)入內(nèi)存繼續(xù)排序。這一過(guò)程需要反復(fù)進(jìn)行，直到全部記錄排出次序?yàn)橹?。顯然，內(nèi)部排序是外部排序的基礎(chǔ)，本章先介紹內(nèi)部排序的各種方法，最后再討論外部排序。 2022/7/2662022/7/26710.2 插入排序 2022/7/268 插入

4、排序的基本思想是：每次將一個(gè)待排序的記錄，按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子表中的適當(dāng)位置，直到全部記錄插入完成為止。也就是說(shuō)，將待序列表分成左右兩部分，左邊為有序表（有序序列），右邊為無(wú)序表（無(wú)序序列）。整個(gè)排序過(guò)程就是將右邊無(wú)序表中的記錄逐個(gè)插入到左邊的有序表中，構(gòu)成新的有序序列。根據(jù)不同的插入方法，插入排序算法主要包括：直接插入排序、折半插入排序、表插入排序和希爾排序等。本章重點(diǎn)介紹直接插入排序、折半插入排序和希爾排序。（P265-271）10.2.1 直接插入排序 2022/7/269 直接插入排序(Insertion Sort)是所有排序方法中最簡(jiǎn)單的一種排序方法。其基本原理是順

5、次地從無(wú)序表中取出記錄ri(1in)，與有序表中記錄的關(guān)鍵字逐個(gè)進(jìn)行比較，找出其應(yīng)該插入的位置，再將此位置及其之后的所有記錄依次向后順移一個(gè)位置，將記錄ri插入其中。向有序表中插入記錄，主要完成如下操作：(1) 搜索插入位置。(2) 移動(dòng)插入點(diǎn)及其以后的記錄空出插入位置。(3) 插入記錄。2022/7/2610 假設(shè)將n個(gè)待排序的記錄順序存放在長(zhǎng)度為n+1的數(shù)組r1rn 中。r0作為輔助空間，用來(lái)暫時(shí)存儲(chǔ)需要插入的記錄，起監(jiān)視哨的作用(臨時(shí)保存，防止被覆蓋或出界)。直接插入排序算法如下:2022/7/2611 顯然，開(kāi)始時(shí)有序表中只有1個(gè)記錄r1，然后需要將r2rn的記錄依次插入到有序表中，總

6、共要進(jìn)行n-1次插入操作。 首先從無(wú)序表中取出待插入的第i個(gè)記錄ri，暫存在r0中；然后將r0.key依次與ri-1.key，ri-2.key，進(jìn)行比較，如果r0.keyri-j.key（1ji-1），則將ri-j后移一個(gè)單元；如果r0.keyri-j.key，則找到r0插入的位置i-j+1，此位置已經(jīng)空出，將r0 (即ri)記錄直接插入即可。如此不斷進(jìn)行，直到完成記錄rn的插入排序，整個(gè)序列變成按關(guān)鍵字非遞減的有序序列為止。 在搜索插入位置的過(guò)程中，r0.key與ri-j.key進(jìn)行比較時(shí)，如果j=i，則循環(huán)條件 r0.keyri-j.key不成立，從而退出for循環(huán)。由此可見(jiàn)r0起到了監(jiān)視

7、哨的作用，避免了數(shù)組下標(biāo)的出界。 2022/7/26122022/7/2613空間性能：該算法僅需要一個(gè)記錄的輔助存儲(chǔ)空間，空間復(fù)雜度為O(1)。時(shí)間性能：一般情況下，時(shí)間復(fù)雜度為O(n2)。穩(wěn)定性：由于該算法在搜索插入位置時(shí)遇到關(guān)鍵字值相等的記錄時(shí)就停止操作，不會(huì)把關(guān)鍵字值相等的兩個(gè)數(shù)據(jù)交換位置，所以該算法是穩(wěn)定的。 10.2.2 折半插入排序 2022/7/2614 直接插入排序的基本操作是在有序表中進(jìn)行查找和插入，而在有序表中查找插入位置，可以通過(guò)折半查找的方法實(shí)現(xiàn)，由此進(jìn)行的插入排序稱(chēng)之為折半插入排序。 所謂折半查找，就是在插入ri時(shí)（此時(shí)r1，r2，ri-1已排序），取ri/2的關(guān)鍵

8、字與ri的關(guān)鍵字進(jìn)行比較（i/2 表示取不大于i/2的最大整數(shù)），如果KiKi/2，i的插入位置只能在r1和ri/2 之間，則在r1和ri/2-1之間繼續(xù)進(jìn)行折半查找，否則在ri/2+1和ri-1 之間進(jìn)行折半查找。如此反復(fù)直到最后確定插入位置為止。折半查找的過(guò)程是以處于有序表中間位置記錄的關(guān)鍵字和Ki比較，經(jīng)過(guò)一次比較，便可排除一半記錄，把可插入的區(qū)間縮小一半，故稱(chēng)為折半。 2022/7/2615 設(shè)置始指針low，指向有序表的第一個(gè)記錄，尾指針high，指向有序表的最后一個(gè)記錄，中間指針mid指向有序表中間位置的記錄。每次將待插入記錄的關(guān)鍵字與mid位置記錄的關(guān)鍵字進(jìn)行比較，從而確定待插入

9、記錄的插入位置。折半插入排序算法如下： 2022/7/2616【例】待排序記錄的關(guān)鍵字為：28，13，72，85，39，41，6，20，在前7個(gè)記錄都已排好序的基礎(chǔ)上，采用折半插入第8個(gè)記錄的比較過(guò)程如圖所示。 圖 折半插入排序 2022/7/2617 折半插入排序減少了關(guān)鍵字間的比較次數(shù)，但記錄的移動(dòng)次數(shù)不變。因此折半插入排序的時(shí)間復(fù)雜度仍為O(n2)。折半插入排序的空間復(fù)雜度與直接插入排序相同。折半插入排序也是一個(gè)穩(wěn)定的排序方法。 10.2.3 希爾排序 2022/7/2618 希爾排序（shells sort）又稱(chēng)縮小增量排序(Diminishing Increment Sort)。它是

10、希爾（D.L.Shell）于1959年提出的插入排序的改進(jìn)算法。如前所述，直接插入排序算法的時(shí)間性能取決于數(shù)據(jù)的初始特性，一般情況下，它的時(shí)間復(fù)雜度為O(n2)。但是當(dāng)待排序列為正序或基本有序時(shí)，時(shí)間復(fù)雜度則為O(n)。因此，若能在一次排序前將排序序列調(diào)整為基本有序，則排序的效率就會(huì)大大提高。正是基于這樣的考慮，希爾提出了改進(jìn)的插入排序方法。 希爾排序的基本思想是：先將整個(gè)待排記錄序列分割成若干小組（子序列），分別在組內(nèi)進(jìn)行直接插入排序，待整個(gè)序列中的記錄“基本有序”時(shí)，再對(duì)全體記錄進(jìn)行一次直接插入排序。希爾排序的具體步驟如下： 2022/7/2619 （1）首先取一個(gè)整數(shù)d1n，稱(chēng)之為增量，

11、將待排序的記錄分成d1個(gè)組，凡是距離為d1倍數(shù)的記錄都放在同一個(gè)組，在各組內(nèi)進(jìn)行直接插入排序，這樣的一次分組和排序過(guò)程稱(chēng)為一趟希爾排序。 （2）再設(shè)置另一個(gè)新的增量d2d1，采用與上述相同的方法繼續(xù)進(jìn)行分組和排序過(guò)程。 （3）繼續(xù)取di+1r2.key，就交換記錄r1和r2在序列中的位置；然后繼續(xù)對(duì)r2.key和r3.key進(jìn)行比較，并作相同的處理；重復(fù)此過(guò)程，直到關(guān)鍵字rn-1.key和rn.key比較完成。其結(jié)果是n個(gè)記錄中關(guān)鍵字最大的記錄被交換到序列的最后一個(gè)記錄的位置上，即具有最大關(guān)鍵字的記錄被“沉”到了最后，這個(gè)過(guò)程被稱(chēng)為一趟冒泡排序。 然后進(jìn)行第二趟冒泡排序，對(duì)序列表中前n-1個(gè)記

12、錄進(jìn)行同樣的操作，使序列表中關(guān)鍵字次大的記錄被交換到序列的n-1位置上；第i趟冒泡排序是從R1到Rn-i+1依次比較相鄰兩個(gè)記錄的關(guān)鍵字，并在“逆序”時(shí)交換相鄰記錄，其結(jié)果是這n-i+1個(gè)記錄中關(guān)鍵字最大的記錄被10.3.1 冒泡排序2022/7/2626交換到n-i+1位置上。每一趟排序都有一個(gè)相對(duì)大的數(shù)據(jù)被交換到后面，就像一塊塊“大”石頭不斷往下沉，最大的總是最早沉下；而具有較小關(guān)鍵字的記錄則不斷向上（前）移動(dòng)位置，就像水中的氣泡逐漸向上飄浮一樣，冒到最上面的是關(guān)鍵字值最小的記錄。所以把這種排序方法稱(chēng)為冒泡排序。對(duì)有n個(gè)記錄的序列最多做n-1趟冒泡就會(huì)把所有記錄依關(guān)鍵字大小排好序 如果在某

13、一趟排序中都沒(méi)有發(fā)生相鄰記錄的交換，表示在該趟之前已達(dá)到排序的目的，整個(gè)排序過(guò)程可以結(jié)束。在操作實(shí)現(xiàn)時(shí)，常用一個(gè)標(biāo)志位flag標(biāo)示在第i趟是否發(fā)生了交換，若在第i趟發(fā)生過(guò)交換，則置flag=false（或0）；若第i趟沒(méi)有發(fā)生交換，則置flag=true（或1），表示在第i-1趟已經(jīng)達(dá)到排序目的，可結(jié)束整個(gè)排序過(guò)程。 2022/7/2627算法描述如下：#define False 0#define True 1typedef int keytype;void Bubble_Sort(RecType R,int n) /用冒泡排序?qū)1Rn記錄排序 int i,j,flag=0;for(i=1;

14、 in; i+) flag=1 ; /每趟比較前設(shè)置flag=1，假定該序列已有序 for(j=1;j=n-i;j+) if(Rj+1.keyRj.key) flag=0; /如果有逆序的則置flag=0 R0=Rj; Rj=Rj+1; Rj+1=R0; if(flag=1) return; /flag為T(mén)rue則表示序列已有序，可結(jié)束排序過(guò)程 在該算法中，外層循環(huán)控制排序的執(zhí)行趟數(shù)，內(nèi)層循環(huán)用于控制在一趟冒泡排序中相鄰記錄間的比較和交換。2022/7/262810.3.2 快速排序 2022/7/26291快速排序的基本思想 快速排序的基本思想是：從待排記錄序列中任取一個(gè)記錄ri作為樞軸（通

15、常取序列中的第一個(gè)記錄，又稱(chēng)基準(zhǔn)），將所有記錄分成兩個(gè)序列分組，使排在ri之前的序列分組的記錄關(guān)鍵字都小于等于樞軸記錄的關(guān)鍵字值ri.key，排在ri之后的序列分組的記錄關(guān)鍵字都大于ri.key，形成以ri為分界的兩個(gè)分組，此時(shí)樞軸記錄ri的位置就是它的最終排序位置。此趟排序稱(chēng)為第一趟快速排序。然后分別對(duì)兩個(gè)序列分組重復(fù)上述過(guò)程，直到所有記錄排在相應(yīng)的位置上。 2022/7/26302選取樞軸 在快速排序中，選取樞軸常用的方法有：（1）選取序列中第一個(gè)記錄的關(guān)鍵字值作為樞軸關(guān)鍵字。這種選擇方法簡(jiǎn)單。但是當(dāng)序列中的記錄已基本有序時(shí)，這種選擇往往使兩個(gè)序列分組的長(zhǎng)度不均勻，不能改進(jìn)排序的時(shí)間性能。

16、（2）選取序列中間位置記錄的關(guān)鍵字值作為樞軸關(guān)鍵字。（3）比較序列中始端、終端及中間位置上記錄的關(guān)鍵字值，并取這三個(gè)值中居中的一個(gè)作為樞軸關(guān)鍵字。 為了敘述方便，在下面的快速排序中，選取第一個(gè)記錄的關(guān)鍵字作為樞軸關(guān)鍵字。 2022/7/26313快速排序的實(shí)現(xiàn) 2022/7/2632一趟快速排序的算法實(shí)現(xiàn) P2742022/7/2633教材P275，圖10.72022/7/2634快速排序算法的遞歸實(shí)現(xiàn)快速排序算法時(shí)間復(fù)雜度分析見(jiàn)教材P276-27710.4 選擇排序 2022/7/263510.4.1 簡(jiǎn)單選擇排序 (1)每次從待排記錄序列中選出關(guān)鍵字最小的記錄； (2)將它與待排記錄序列第

17、一位置的記錄交換后，再將其“插入”已排序記錄序列(初始為空)； (3)不斷重復(fù)過(guò)程(1)和(2)，就不斷地從待排記錄序列中剩下的(n-1，n-2，2)個(gè)記錄中選出關(guān)鍵字最小的記錄與該區(qū)第1位置的記錄交換(該區(qū)第1個(gè)位置不斷后移，該區(qū)記錄逐漸減少)，然后把第1位置的記錄不斷 “插入” 已排序記錄序列之后。經(jīng)過(guò)n-1次的選擇和多次交換后，R1 Rn就排成了有序序列，整個(gè)排序過(guò)程結(jié)束。具有n個(gè)記錄的待排記錄序列要做n-1次的選擇和交換才能成為有序表。 2022/7/2636void Select_Sort(RecType R,int n) int i,j,k; RecType temp; for(i

18、=1;in;i+) /進(jìn)行n-1趟排序，每趟選出1個(gè)最小記錄 k=i; /假定起始位置為最小記錄的位置 for(j=i+1;j=n;j+) /查找最小記錄 if(Rj.keyRk.key) k=j; if(i!=k) /如果k不是假定位置，則交換 temp=Rk; /交換記錄 Rk=Ri; Ri=temp; 本算法中有兩重循環(huán)：外循環(huán)用于控制排序的次數(shù)，內(nèi)循環(huán)用于查找當(dāng)前待排記錄序列中關(guān)鍵字最小的記錄。 2022/7/2637【例】采用簡(jiǎn)單選擇排序?qū)σ韵?個(gè)記錄進(jìn)行排序簡(jiǎn)單選擇排序示例 10.4.2 堆排序 2022/7/26382022/7/26392022/7/26402022/7/264

19、12022/7/2642堆排序算法（P282） 篩選算法（P282） 10.5 歸并排序 2022/7/26432-路歸并排序的遞歸算法 2022/7/264410.6 外部排序 2022/7/2645 外部排序指的是大文件的排序，即待排序的記錄存儲(chǔ)在外存儲(chǔ)器上，由于文件一般都很大，無(wú)法把整個(gè)文件的所有記錄同時(shí)調(diào)入內(nèi)存中進(jìn)行排序，即無(wú)法進(jìn)行內(nèi)部排序，從而需要研究外存設(shè)備上的排序技術(shù)，我們稱(chēng)這種排序?yàn)橥獠颗判?。外部排序的思想就是將排序過(guò)程分為兩個(gè)相對(duì)獨(dú)立的階段。首先，按內(nèi)存的大小，將外存上含n個(gè)記錄的文件分成若干個(gè)長(zhǎng)度為l的子文件或段，依次讀入內(nèi)存，并利用有效的內(nèi)部排序方法對(duì)它們進(jìn)行排序，將排序

20、后得到的有序子文件重寫(xiě)回外存，通常稱(chēng)這些有序子文件為歸并段，于是在外存中形成許多歸并段；最后再將這些歸并段逐趟歸并，使得有序的歸并段逐漸擴(kuò)大，直至得到一個(gè)有序文件為止。 10.6.1外部排序過(guò)程 2022/7/2646 外部排序需要經(jīng)常和外存打交道，因此外部排序速度比內(nèi)部排序速度相差甚遠(yuǎn)。要想提高外部排序速度，應(yīng)盡量減少與外存打交道的次數(shù)，同時(shí)也與外部設(shè)備本身的存取特性有密切關(guān)系。假設(shè)有一個(gè)含有10 000個(gè)記錄的文件，首先通過(guò)10次內(nèi)部排序得到10個(gè)初始?xì)w并段R1R10，其中每一段含有1000個(gè)記錄。然后對(duì)它們進(jìn)行兩兩歸并，直至得到一個(gè)有序文件為止。 如圖8-14可見(jiàn)，由10個(gè)初始?xì)w并段到一

21、個(gè)有序文件共進(jìn)行四趟歸并，每趟歸并從m個(gè)歸并段得到m/2個(gè)歸并段。這種歸并方法稱(chēng)為2-路平衡歸并。啟動(dòng)外存儲(chǔ)器需要進(jìn)行八次讀寫(xiě)，啟動(dòng)一次外存所需時(shí)間為毫秒級(jí)，而內(nèi)部排序僅在毫微秒級(jí)，相差106級(jí)別。由此可見(jiàn)，提高外排序的有效措施在于減少歸并趟數(shù)。顯然，增加歸并路數(shù)，采用多路平衡歸并可提高外排序的效率。 2022/7/2647 2-路平衡歸并過(guò)程 10.6.2多路平衡歸并 2022/7/2648 假定對(duì)n個(gè)記錄進(jìn)行k-路平衡歸并，令n個(gè)記錄分布在k個(gè)歸并段上。若對(duì)m個(gè)初始?xì)w并段進(jìn)行k-路平衡歸并，則歸并趟數(shù)s為 s= logkm 顯然，歸并后的第一個(gè)記錄應(yīng)是k個(gè)歸并段中關(guān)鍵字最小的記錄，需要比較

22、k-1次；每趟歸并n個(gè)記錄需要進(jìn)行(n-1) (k-1)次比較，則s趟歸并總共需要的比較次數(shù)為：s(n-1) (k-1)= logkm (n-1) (k-1)= log2m (n-1) (k-1) / log2k 其中，log2m (n-1)在初始?xì)w并段個(gè)數(shù)m與記錄個(gè)數(shù)n一定時(shí)為常量，而(k-1)/ log2k隨k的增大而增大，從而使內(nèi)部歸并的時(shí)間增大。雖然歸并路數(shù)k的增大，會(huì)減少歸并趟數(shù)s。但當(dāng)(k-1)/ log2k增大到一定的程度時(shí)，就會(huì)抵消掉由于歸并趟數(shù)減少而贏得的磁盤(pán)讀寫(xiě)時(shí)間。10.7 各種排序方法的比較 2022/7/2649 在前面幾節(jié)中討論了內(nèi)部排序和外部排序的方法。對(duì)于內(nèi)部排

23、序主要介紹了五大類(lèi)排序方法：插入排序（直接插入排序、折半插入排序和希爾排序）、交換排序（冒泡排序和快速排序）、選擇排序（簡(jiǎn)單選擇排序和堆排序）、歸并排序和基數(shù)排序。詳細(xì)討論了各種排序方法的基本原理，并從時(shí)間復(fù)雜性、空間復(fù)雜性以及排序的穩(wěn)定性三方面討論了各種排序方法的時(shí)效性，介紹了各排序方法的實(shí)現(xiàn)算法及其存在的優(yōu)缺點(diǎn)。 如果待排序的數(shù)據(jù)量很小，最好選擇編程簡(jiǎn)單的排序算法，因?yàn)樵谶@種情況下采用編程復(fù)雜、效率較高的排序方法所能節(jié)約的計(jì)算機(jī)時(shí)間是很有限的。反之，如果待處理的數(shù)據(jù)量很大，特別是當(dāng)排序過(guò)程作為應(yīng)用程序的一部分需要經(jīng)常執(zhí)行時(shí)，就應(yīng)該認(rèn)真分析和比較各種排序方法，從中選出運(yùn)行效率最高的方法。20

24、22/7/2650 下面具體比較一下各種排序方法，以便實(shí)現(xiàn)不同的排序處理。 (1) 插入排序的原理：向有序序列中依次插入無(wú)序序列中待排序的記錄，直到無(wú)序序列為空，對(duì)應(yīng)的有序序列即為排序的結(jié)果，其主旨是“插入”。 (2) 交換排序的原理：先比較大小，如果逆序就進(jìn)行交換，直到有序。其主旨是“若逆序就交換”。 (3) 選擇排序的原理：先找關(guān)鍵字最小的記錄，再放到已排好序的序列后面，依次選擇，直到全部有序，其主旨是“選擇”。 (4) 歸并排序的原理：依次對(duì)兩個(gè)有序子序列進(jìn)行“合并”，直到合并為一個(gè)有序序列為止，其主旨是“合并”。 (5) 基數(shù)排序的原理：按待排序記錄的關(guān)鍵字的組成成分進(jìn)行排序的一種方法，即依次比較各個(gè)記錄關(guān)鍵字相應(yīng)“位”的值，進(jìn)行排序，直到比較完所有的“位”，即得到一個(gè)有序的序列。 各種排序方法的工作原理不同，對(duì)應(yīng)的性能也有很大的差別，下面通過(guò)一個(gè)表格可以看到