數據結構與算法分析

APracticalIntroductionto

DataStructuresandAlgorithmAnalysis

陳星

第三部分排序和檢索

第7章內排序。第8章文件管理和外排序。第9章檢索。第10章索引技術。參考文獻：DataStructuresandAlgorithmAnalysis，C.A.Shaffer，電子工業出版社2002。數據結構（C語言版），嚴蔚敏等，清華大學出版社1997。數據結構—C++與面向對象的途徑，張乃孝,裘宗燕，高等教育出版社，2001。第7章內排序在計算機主存內對一組記錄進行排序的標準算法。先介紹三種簡單但較慢（Θ(n2)）的算法.1.插入排序。

2.起泡（冒泡排序）。

3.選擇排序。再介紹幾種復雜但較快的算法.

如Shell排序、快速排序、堆排序、歸并排序……排序操作中的基本運算.1.比較2.交換排序方法插入類排序選擇類排序交換類排序歸并排序插入排序希爾排序選擇排序堆排序快速排序分配類排序：基數排序起泡排序排序技術種類

按平均時間將排序分為四類：（1）平方階(O(n2))排序

一般稱為簡單排序，例如直接插入、直接選擇和冒泡排序（2）線性對數階(O(nlogn))排序

如快速、堆和歸并排序；

（3）O(n1+￡)階排序

￡是介于0和1之間的常數，即0<￡<1，如希爾排序；

（4）線性階(O(n))排序

如分配和基數排序。排序技術種類7.1排序術語及記號記錄之間通過一個比較器類進行比較。關鍵字是數據元素中的某個數據項。每個記錄中都有一個關鍵碼域(key)。比較器類就是對該關鍵碼進行比較;設對每一種記錄類型都已定義Swap函數。思考?

有一堆雜亂無章的撲克牌,要求你從A到2的順序在手上理好。想一想你會采用什么方法理好牌？

7.2三種代價為Θ（n2）的排序方法算法簡單、易懂、易于實現，但速度慢。7.2.1插入排序原理：將無序序列中的各元素依次與前面已排序的子序列進行比較，將它插入到有序子序列中正確的位置。步驟：(1)首先將只含第1個元素的看成有序表。

(2)從線性表的第2個元素直到最后一個元素，依次將每個元素插入前面已經有序的子表中。

(3)插入第j個元素的方法：將j放在變量T中，從有序子表（原線性表的前j-1個元素）的最后一個元素開始，往前逐個與T比較，將大于T的元素無向后移一個位置，直到發現一個元素不大于T為止，將T插入到剛移出的空位置上，有序子表的長度增加為j。插入排序比較1次交換1次

比較6次交換5次比較3次交換2次比較5次交換4次比較2次交換1次比較3次交換3次比較2次交換2次比較22次交換18次

插入排序的代價分析時間代價：最差情況下(原始紀錄全是逆序)：需要的比較次數：Θ(n2)

最佳情況下(原始紀錄已經有序)：只需要n-1次比較；Θ(n)平均情況下：平均的時間代價是最差情況的一半，仍為Θ(n2)

空間代價：只需要一個暫存單元:Θ(1)

7.2.2起泡排序起泡排序的基本思想對所有相鄰記錄的關鍵字值進行比效，如果是逆序（a[j]>a[j+1]），則將其交換，最終達到有序化。其處理過程為：對待排序的記錄序列從后向前（或從前向后）進行掃描。依次比較相鄰記錄的關鍵字。交換比較中發現的逆序。因此關鍵字值小的記錄左移，關鍵字值大的記錄右移。一次掃描后，最小值移動序列的頂端。做n-1遍從后向前（或從前向后）的掃描和逆序交換，或直到未發現逆序為止。起泡排序算法P144-145算法：template<classElem,classComp>voidbubsort(ElemA[],intn){for(inti=0;i<n-1;i++)for(intj=n-1;j>i;j--)if(Comp::lt(A[j],A[j-1]))swap(A,j,j-1);}教科書上有錯起泡排序代價分析比較次數：時間代價：Θ(n2)

需增加一個輔助單元進行交換；空間代價：Θ(1)問：如何改進P144-145算法，減少起泡排序的比較和交換次數？7.2.3選擇排序基本思想：掃描整個線性表，從中選出最小的元素，將它交換到表的最前面；然后對剩下的子表采用同樣的辦法，直到子表空為止。template<classElem,classComp>voidselsort(ElemA[],intn){for(inti=0;i<n-1;i++){intlowindex=i;//Rememberitsindexfor(intj=n-1;j>i;j--)//Findleastif(Comp::lt(A[j],A[lowindex]))lowindex=j;//Putitinplaceswap(A,i,lowindex);}}選擇排序和起泡排序的比較相同：表面上來看，一輪比較和交換后，最小值都放到了頂部；實質上而言，選擇排序就是起泡排序；不同：選擇排序中最小元素一次交換到位；選擇排序的交換次數要比起泡排序少得多。起泡排序選擇排序選擇排序的時間代價選擇排序實質上是起泡排序。選擇排序比較次數：Θ(n2)交換的次數比起泡排序少。因此，總的時間代價為Θ(n2)

。交換指針只交換指針，不移動記錄本身，換來更高的效率,特別當記錄很大的時候。可以降低排序算法中交換記錄所需要的時間。7.2.4交換排序算法的時間代價InsertionBubbleSelectionComparisons:BestCase(n)Q(n2)Q(n2)AverageCaseQ(n2)Q(n2)Q(n2)WorstCaseQ(n2)Q(n2)Q(n2)SwapsBestCase00(n)AverageCaseQ(n2)Q(n2)(n)WorstCaseQ(n2)Q(n2)(n)這些排序方法只比較相鄰的記錄。交換排序的最小時間代價(平均來說):考慮一個有n個元素的序列L；L中有n(n-1)/2對不同的元素，每一對都可能是一個逆置；平均而言，一半正序，一半逆序(即每個序列有n(n-1)/4對逆置序列)；相鄰元素交換只能處理掉一個逆序；任何一種將比較限制在相鄰兩個元素之間進行的交換算法的平均時間代價都是Q

(n2)。7.3Shell排序又稱為縮小增量排序。基本思想：將整個線性表進行分割，相隔某個增量h的元素構成一個子表，對子表分別進行插入排序，并逐漸減小增量h。最后當h為1時，進行一次插入排序，排序完成。希爾排序中，確定增量的大小是關鍵，但迄今未能得到解決。增量序列一般取ht=n/2k(k=1,2,3,…,[logn])，其中n為待排序列的長度。

增量序列也可以以每次除以3來選取（…，121，40，13，4，1）希爾排序例子對關鍵字序列<07,19,24,13,31,08,82,18,44,63,05,29>

進行希爾排序：該例中n=12，[logn]=[log12]=3；取增量系列為ht=12/2k(k=1,2,3)，即h1=12/2=6,h2=12/4=3,h3=12/8≈1071924133108821844630529h1=6071824130508821944633129結果h2=3071824130508821944633129結果070508131824631929823144h3=1結果070508131824631929823144050708131819242931446382Shell排序分析相當困難，其效率依賴于增量序列的選取。可以認為Shell排序的平均時間代價為Θ(n1.5)希爾排序的空間代價為Θ(1)；同插入排序一樣，希爾排序也只需要一個記錄大小的輔助空間，用于暫存當前待插入的記錄。當n為中等規模大小時Shell排序是不錯的選擇二叉查找樹中序遍歷有序序列888082688582

7571778880826885827177757.4快速排序分治法(divideandconquer)的思想：根結點將左、右子樹分開，形成：左子樹<根右子樹二叉查找樹中序周游可得到有序序列，但弊端多：存儲占用大量結點空間、二叉樹不平衡時插入時間代價大。

快速排序以一種更有效的方法實現了“分治法”思想。基本思想：從待排序序列中選取一個元素，以該關鍵字值為軸值(pivot)，將待排序列分割為兩個子序列。軸值左側子序列中記錄都小于或等于軸值，右側子序列中記錄都大于或等于軸值。對子序列反復進行分割，直到每個子序列的元素個數為1。整個線性表變成了有序表。快速排序以60為軸值，一趟分割后結果以6為軸值，二趟分割后結果以73為軸值，二趟分割后結果關鍵技術：線性表的分割考慮：1、大（小）的元素要移動到表的后（前）半部分。2、在原表中移動，要考慮空位。具體步驟：附設兩個指針i和j，初值分別指向第一個記錄和最后一個記錄，將分割中項保存在臨時變量T中

，再將第一個記錄移動分割中項的位置。首先從j所指位置起向前搜索，找到小于T的記錄移動到i指向的位置，然后從i所指位置起向后搜索，找到大于T的記錄移動到j指向的位置。重復這兩步直至i=j為止。快速排序的步驟123 456783865764913273997

j

i分割中項T快速排序的分割方法將序列38、65、76、49、13、27、39、97用快速排序的方法進行排序。整個表：從38，97和49中取出中項49作為分割中項T進行快速排序123 456783865764913273997123 456783865764913273997

j

i分割中項T＝49快速排序的分割方法將序列38、65、76、49、13、27、39、97用快速排序的方法進行排序。將分割中項49保存在變量T中，將i所指向的記錄38移到分割中項位置。123 4567865763813273997123 456783865764913273997

j

i分割中項T＝49快速排序的分割方法將序列38、65、76、49、13、27、39、97用快速排序的方法進行排序。首先指針j指向的記錄與T進行比較。97>T，不交換。123 4567865763813273997123 456783865764913273997

j

i分割中項T＝49快速排序的分割方法將序列38、65、76、49、13、27、39、97用快速排序的方法進行排序。指針j繼續向前掃描。39<T。123 4567865763813273997123 456783865764913273997

j

i分割中項T＝49快速排序的分割方法將序列38、65、76、49、13、27、39、97用快速排序的方法進行排序。將39移動i所指位置。123 4567865763813273997123 456783865764913273997

j

i分割中項T＝49快速排序的分割方法將序列38、65、76、49、13、27、39、97用快速排序的方法進行排序。指針i開始向后掃描，65>T。123 4567865763813273997123 456783865764913273997

j

i分割中項T＝49快速排序的分割方法將序列38、65、76、49、13、27、39、97用快速排序的方法進行排序。將65移動j所指位置，指針j開始向前掃描。123 4567865763813273997123 456783865764913273997

j

i分割中項T＝49快速排序的分割方法將序列38、65、76、49、13、27、39、97用快速排序的方法進行排序。27<T123 4567865763813273997123 456783865764913273997

j

i分割中項T＝49快速排序的分割方法將序列38、65、76、49、13、27、39、97用快速排序的方法進行排序。將27移動i所指位置，指針i開始向后掃描。123 4567865763813273997123 456783865764913273997

j

i分割中項T＝49快速排序的分割方法將序列38、65、76、49、13、27、39、97用快速排序的方法進行排序。76>T。123 4567865763813273997123 456783865764913273997

j

i分割中項T＝49快速排序的分割方法將序列38、65、76、49、13、27、39、97用快速排序的方法進行排序。將76移動j所指位置，指針j開始掃描。123 4567865763813273997123 456783865764913273997

j

i分割中項T＝49快速排序的分割方法將序列38、65、76、49、13、27、39、97用快速排序的方法進行排序。13<T。123 4567865763813273997123 456783865764913273997

j

i分割中項T＝49快速排序的分割方法將序列38、65、76、49、13、27、39、97用快速排序的方法進行排序。123 4567865763813273997將13移動i所指位置，指針i開始向后掃描。123 456783865764913273997

j

i分割中項T＝49快速排序的分割方法將序列38、65、76、49、13、27、39、97用快速排序的方法進行排序。123 456786576381327399738<T，不移動，指針i繼續向后掃描。123 456783865764913273997

j

i分割中項T＝49快速排序的分割方法將序列38、65、76、49、13、27、39、97用快速排序的方法進行排序。123 4567865763813273997指針i和j相遇，將分割中項填入i和j所指位置。一趟分割結束。49快速排序的時間代價最佳情況:分割中項每次都為序列中記錄中間值，時間代價為Θ(nlogn);最環情況:分割中項每次都為序列中記錄的最大值或最小值，時間代價為Θ(n2);平均情況:平均時間代價Θ(nlogn)。快速排序的空間代價快速排序每次只能對一個子表進行排序，已劃分的另一個子表需要用棧來記錄下來，留待以后進行排序。通常情況下空間代價(記錄子表的棧)為Θ(logn);最壞情況下空間代價為Θ(n);快速排序的優化軸值pivot的選取第一個或最后一個記錄的關鍵字易退化為起泡算法。隨機選取值開銷大數組中間點三者取中法首中尾三個記錄的中間值用于小子表的更佳算法劃分過程沒有必要劃分到子表長度為1的情況，當子表長度小于某個值時，調用其他排序方法會快點。消除遞歸將遞歸改成非遞歸算法。速度加快。快速排序總結快速排序是一個遞歸的過程。在遞歸調用時需要占據一定的存儲空間用來保存每一層遞歸調用時的必要信息。快速的效率與起泡排序相比有很大地提高。在起泡排序過程中是對相鄰兩個記錄進行關鍵字比較和互換的，這樣每次交換記錄后，只能改變一對逆序記錄；而快速排序則從待排序記錄的兩端開始進行比較和交換，并逐漸向中間靠攏，每經過一次交換，有可能改變幾對逆序記錄，從而加快了排序速度。到目前為止快速排序是平均速度最快的一種排序方法，歸并排序歸并是指將兩個或兩個以上的有序表合并成一個新的有序表。歸并排序的基本思想是將一個具有n個待排序記錄的序列看成是n個長度為1的有序序列，然后進行兩兩歸并，得到n/2個長度為2的有序序列，再進行兩兩歸并，得到n/4個長度為4的有序序列，如此重復，直至得到一個長度為n的有序序列為止。歸并排序的關鍵技術

－將兩個有序序列合并為一個有序序列方法：順序比較兩個表中的元素，將值小者移入合并后的新表中，反復如此，直至所有元素都移入新表。0123 44913659776780AB0123 4567Cijk設置指針i,j,k分別指向A,B,C的第一個單元。歸并排序的關鍵技術

－將兩個有序序列合并為一個有序序列方法：設置指標，順序比較兩個表中的元素，將值小者移入合并后的新表中，反復如此，直至所有元素都移入新表。0123 44913659776780AB0123 4567Cijk7<13，移走7，指標j和k后移一位。7歸并排序的關鍵技術

－將兩個有序序列合并為一個有序序列方法：設置指標，順序比較兩個表中的元素，將值小者移入合并后的新表中，反復如此，直至所有元素都移入新表。0123 449659776780AB0123 4567Cijk

13<76，移走13，指標i和k后移一位。713歸并排序的關鍵技術

－將兩個有序序列合并為一個有序序列方法：設置指標，順序比較兩個表中的元素，將值小者移入合并后的新表中，反復如此，直至所有元素都移入新表。0123 4659776780AB0123 4567Cijk

49<76，移走13，指標i和k后移一位。71349歸并排序的關鍵技術

－將兩個有序序列合并為一個有序序列方法：設置指標，順序比較兩個表中的元素，將值小者移入合并后的新表中，反復如此，直至所有元素都移入新表。0123 49776780AB0123 4567Cijk

65<76，移走65，指標i和k后移一位。7134965歸并排序的關鍵技術

－將兩個有序序列合并為一個有序序列方法：設置指標，順序比較兩個表中的元素，將值小者移入合并后的新表中，反復如此，直至所有元素都移入新表。0123 497780AB0123 4567Cijk

76<97，移走76，指標j和k后移一位。713496576歸并排序的關鍵技術

－將兩個有序序列合并為一個有序序列方法：設置指標，順序比較兩個表中的元素，將值小者移入合并后的新表中，反復如此，直至所有元素都移入新表。0123 4977AB0123 4567Cijk

80<97，移走80。71349657680歸并排序的關鍵技術

－將兩個有序序列合并為一個有序序列方法：設置指標，順序比較兩個表中的元素，將值小者移入合并后的新表中，反復如此，直至所有元素都移入新表。0123 47AB0123 4567Cijk由于B已移空，停止比較，將A中剩余元素全部移到C中。7134965768097歸并排序的偽代碼Listmergesort(Listinlist){if(length(inlist)<=1)returninlist;Listl1=halfoftheitemsfrominlist;Listl2=otherhalfofitemsfrominlist;returnmerge(mergesort(l1),mergesort(l2));}template<classElem,classComp>voidmergesort(ElemA[],Elemtemp[],intleft,intright){if((right-left)<=THRESHOLD){

inssort<Elem,Comp>(&A[left],right-left+1);return;}inti,j,k,mid=(left+right)/2;if(left==right)return;mergesort<Elem,Comp>(A,temp,left,mid);mergesort<Elem,Comp>(A,temp,mid+1,right);for(i=mid;i>=left;i--)temp[i]=A[i];for(j=1;j<=right-mid;j++)temp[right-j+1]=A[j+mid];for(i=left,j=right,k=left;k<=right;k++)if(temp[i]<temp[j])A[k]=temp[i++];elseA[k]=temp[j--];}用插入排序處理較短的數組兩個子數組相向插入，不需要檢查子序列是否處理完成歸并排序的優化實現歸并排序的時/空間代價每次合并的時間代價為Θ(n)；從步長為1開始，整個合并完成需要logn次，總的時間代價為Θ(nlogn)。該時間代價并不依賴于待排數組中數值的相對順序，因此，它也就是歸并排序最佳、平均和最差的運行時間。歸并排序同樣也適用于處理鏈式存儲的待排關鍵字序列.需要與待排序空間等量的輔助空間，空間代價為Θ(n).這是歸并排序的嚴重缺陷。7.4堆排序堆排序耗時：初始建堆時間＋(n-1)?調整一次堆的時間。最初，堆調整的路長決定于樹的深度Θ(logn)，隨著選出結點的增多，待排的堆體積不斷減小，調整的路長也不斷減小，所以調整的時間代價最多為Θ(logn)；即堆排序總的時間為Θ(n)+(n-1)?Θ(logn)，也就是說堆排序的時間代價為Θ(nlogn)；堆排序需要一個輔助空間，即空間代價為Θ(1)。堆排序對原始記錄的排列狀態并不敏感，適用于規模(n)較大的待排序序列。分配排序一個簡單、有效的排序:for(i=0;i<n;i++)B[A[i]]=A[i];關鍵碼B[]用來確定一個記錄在排序中的最終記錄，用“盒子”來存放待排記錄。這種排序方法的時間代價是(n),

但是它只能處理對一個從0到n-1的排列進行排序。擴展分配排序方法一：盒子可變長，允許關鍵碼重復。即數組B中元素為一個鏈表的頭結點.

關鍵碼重復的記錄在一個鏈表中，需要額外進行排序。方法二：允許關鍵碼范圍大于n，先將所有的A[i]放入B中，再依次從關鍵碼B中讀出記錄.B的大小決定于記錄的最大值MaxKeyValue.將所有記錄A[i]放入B中的時間代價是(n)，從B中讀出所有記錄的時間代價是(MaxKeyValue)，故總時間代價是(n+MaxKeyValue)。但是,記錄的規模n和MaxKeyValue之間沒有任何必然聯系,因此,該算法的時間代價可能為(n2)甚至更糟.分配排序的擴展桶式排序

BucketSort每一個“盒子(桶)”中存放一組相關的關鍵碼,然后借助其他排序技術對每一個“桶”中的記錄排序。分桶處理技術＋收尾排序。基數排序將排序關鍵字K看作是由多個關鍵字組成的組合關鍵字，即K=k1k2…kd。每個關鍵字ki表示關鍵字的一位，其中k1為最高位，kd為最低位，d為關鍵字的位數。例如，序列(101,203,567,231,478,352)，可以將每個關鍵字K看成由三個單關鍵字組成，即K=k1k2k3，每個關鍵字的取