數據結構-用面向對象語言描述-殷人昆-第九章

第九章排序主講：楊同峰1概述插入排序交換排序選擇排序基數排序第九章排序2概述排序：將一組雜亂無章的數據按一定的規(guī)律順次排列起來。

3概述排序碼(key):通常數據元素有多個屬性域,即多個數據成員組成,其中有一個屬性域可用來區(qū)分元素,作為排序依據。該域即為排序碼。每個數據表用哪個屬性域作為排序碼，要視具體的應用需要而定。4排序算法的穩(wěn)定性:如果在元素序列中有2個元素r[i]和r[j],它們的排序碼k[i]

==k[j]

,且在排序之前,元素r[i]排在r[j]前面。如果在排序之后,元素r[i]仍在元素r[j]的前面,則稱這個排序方法是穩(wěn)定的,否則稱這個排序方法是不穩(wěn)定的。5內排序:是指在排序期間數據元素全部存放在內存的排序。6外排序:是指在排序期間全部元素個數太多，不能同時存放在內存，必須根據排序過程的要求，不斷在內、外存之間移動的排序。7排序的時間開銷:排序的時間開銷是衡量算法好壞的最重要的標志。排序的時間開銷可用算法執(zhí)行中的數據比較次數與數據移動次數來衡量。8算法運行時間代價的大略估算一般都按平均情況進行估算。對于那些受元素排序碼序列初始排列及元素個數影響較大的，需要按最好情況和最壞情況進行估算。9基本方法是：設待排序元素序列中的元素個數為n。最多作n-1趟，i=1,2,,n-1。在第i趟中從后向前，j=n-1,n-2,,i，順次兩兩比較V[j-1].key和V[j].key。如果發(fā)生逆序，則交換V[j-1]和V[j]。起泡排序(BubbleSort)1021254925*16080123452125*i=149251625160849Exchang=10825*4921Exchang=1i=2i=30816Exchang=125*25211125*012345i=44916Exchang=008252112算法分析第i趟對待排序元素序列V[i-1],V[i],,V[right]進行排序，結果將該序列中排序碼最小的元素交換到序列的第一個位置(i-1)。起泡排序需要一個附加元素以實現元素值的對換。起泡排序是一個穩(wěn)定的排序方法。13最多做n-1趟起泡就能把所有元素排好序。在元素的初始排列已經按排序碼從小到大排好序時，此算法只執(zhí)行一趟起泡，做n-1次排序碼比較，不移動元素。這是最好的情形。最壞的情形是算法執(zhí)行n-1趟起泡,第i趟(1≤in)做n-i次排序碼比較,執(zhí)行n-i次元素交換。在最壞情形下總的排序碼比較次數KCN和元素移動次數RMN為：14插入排序(InsertSorting)基本方法是：每步將一個待排序的元素，按其排序碼大小，插入到前面已經排好序的一組元素的適當位置上,直到元素全部插入為止。15直接插入排序(InsertSort)基本思想是:當插入第i(i≥1)個元素時，前面的V[0],V[1],…,V[i-1]已經排好序。這時，用V[i]的排序碼與V[i-1],V[i-2],…的排序碼順序進行比較，插入位置即將V[i]插入，原來位置上的元素向后順移。16各趟排序結果21254925*1608012345012345temp21254925*160825i=1012345temp21254925*160849i=217012345i=4i=5i=3012345temp21254925*16081621254925*160825*012345temp21254925*1608081821254925*1608012345i=4時的排序過程完成1616012345temp21254925*08164916012345temp21254925*0816i=4j=3i=4j=2192516012345temp214925*08162525*1621254925*0801234516i=4j=1i=4j=0i=4j=-1012345temp21254925*0816211620算法分析設待排序元素個數為currentSize=n,則該算法的主程序執(zhí)行n-1趟。排序碼比較次數和元素移動次數與元素排序碼的初始排列有關。21最好情況下，排序前元素已按排序碼從小到大有序，每趟只需與前面有序元素序列的最后一個元素比較1次，總的排序碼比較次數為n-1,元素移動次數為0。最壞情況下,第i趟時第i個元素必須與前面i個元素都做排序碼比較,并且每做1次比較就要做1次數據移動。則總排序碼比較次數KCN和元素移動次數RMN分別為22平均情況下排序的時間復雜度為o(n2)。直接插入排序是一種穩(wěn)定的排序方法。23希爾排序方法又稱為縮小增量排序。該方法的基本思想是:設待排序元素序列有n個元素,首先取一個整數gap<n作為間隔，將全部元素分為gap個子序列，所有距離為gap的元素放在同一個子序列中，在每一個子序列中分別希爾排序(ShellSort)24 施行直接插入排序。然后縮小間隔gap,例如取gap=gap/2，重復上述的子序列劃分和排序工作。直到最后取gap==1，將所有元素放在同一個序列中排序為止。開始時

gap

的值較大，子序列中的元素較少，排序速度較快;隨著排序進展，gap值逐漸變小,子序列中元素個數逐漸變多，由于前面工作的基礎，大多數元素已基本有序，所以排序速度仍然很快。2521254925*16080123452125*i

=10849Gap=32516492516084925*0821252125*162621254925*160801234521i=20849Gap=22516491625*0821254925*08162125*252721254925*160801234521i

=308Gap=125164925*28算法分析Gap的取法有多種。最初shell提出取gap=n/2，gap=gap/2，直到gap=1。knuth提出取gap=gap/3+1。還有人提出都取奇數為好，也有人提出各gap互質為好。對特定的待排序元素序列，可以準確地估算排序碼的比較次數和元素移動次數。29想要弄清排序碼比較次數和元素移動次數與增量選擇之間的依賴關系，并給出完整的數學分析，還沒有人能夠做到。Knuth利用大量實驗統(tǒng)計資料得出:當n很大時，排序碼平均比較次數和元素平均移動次數大約在n1.25到1.6n1.25的范圍內。這是在利用直接插入排序作為子序列排序方法的情況下得到的。希爾排序是一種不穩(wěn)定的排序方法。30基本思想是任取待排序元素序列中的某個元素(例如取第一個元素)作為基準，按照該元素的排序碼大小，將整個元素序列劃分為左右兩個子序列：左側子序列中所有元素的排序碼都小于或等于基準元素的排序碼快速排序(QuickSort)31右側子序列中所有元素的排序碼都大于基準元素的排序碼基準元素則排在這兩個子序列中間(這也是該元素最終應安放的位置)。然后分別對這兩個子序列重復施行上述方法，直到所有的元素都排在相應位置上為止。32pivotpos：指向基準元素位置，初始位置指向當前序列的第1個元素；i：遍歷指針，初始位置指向pivotpos的下一個元素基準元素定位過程：將當前序列的第1個元素值作為基準元素值，與i指向的元素比較，若大于或等于則i繼續(xù)前行遍歷，若小于則pivotpos先前移一位，然后交換此時的pivotpos與i指向的元素，交換完畢，i繼續(xù)遍歷，重復前述步驟當i遍歷完畢當前序列，交換第1個元素和當前pivotpos指向的元素，完成本趟排序3321254925*16080123452125*i=14925*1625160849pivot08254921i=2i=308162525*21pivotpivotpivot3421254925*160801234525*i=1劃分251625160849pivotpos0825*49081625*2521pivotpos21比較4次交換25,16iipivotpos21比較1次交換49,0849lowpivotpos交換21,0835函數quicksort的平均計算時間是O(nlog2n)。實驗結果表明:就平均計算時間而言，快速排序是內排序方法中最好的一個?？焖倥判蚴且环N不穩(wěn)定的排序方法。對于n較大的平均情況而言,快速排序是“快速”的,但是當n很小時,這種排序方法往往比其它簡單排序方法還要慢。因此，當n很小時可以用直接插入排序方法快速排序的最壞情形為待排序元素已經按排序碼從小到大排好序時36選擇排序基本思想是:每一趟(例如第i趟,i=0,1,…,n-2)在后面n-i個待排序元素中選出排序碼最小的元素，作為有序元素序列的第i個元素。待到第n-2趟作完，待排序元素只剩下1個,就不用再選了。37直接選擇排序(SelectSort)直接選擇排序的基本步驟是：在一組元素V[i]～V[n-1]中選擇具有最小排序碼的元素；若它不是這組元素中的第一個元素,則將它與這組元素中的第一個元素對調;在這組元素中剔除這個具有最小排序碼的元素。在剩下的元素V[i+1]～

V[n-1]中重復執(zhí)行第①、②步,直到剩余元素只有一個為止。3821254925*16080123452125*i=0492516251608490825*4921i=1i=2081625*2521初始最小者08交換21,08最小者16交換25,16最小者21交換49,21394925*01234525*i=42516084925*4921結果i=308162521最小者25*無交換最小者25無交換25211608各趟排序后的結果40i=1時選擇排序的過程012345160825*492125ikj492549250825*1621ikj25*2541490825*211625ikj16<2549250825*1621012345ikj2116k指示當前序列中最小者42直接選擇排序的排序碼比較次數KCN與元素的初始排列無關。設整個待排序元素序列有n個元素，則第i趟選擇具有最小排序碼元素所需的比較次數總是n-i-1次。總的排序碼比較次數為元素移動次數與元素序列初始排列有關。當這組元素初始狀態(tài)是按其排序碼從小到大有序的時候,元素的移動次數達到最少RMN=0，。43最壞情況是每一趟都要進行交換，總的元素移動次數為RMN=3(n-1)。直接選擇排序是一種不穩(wěn)定的排序方法。44基數排序是采用“分配”與“收集”的辦法，用對多排序碼進行排序的思想實現對單排序碼進行排序的方法。以撲克牌排序為例。每張撲克牌有兩個“排序碼”：花色和面值。其有序關系為：花色：

面值：2<3<4<5<6<7<8<9<10<J<Q<K<A基數排序(RadixSort)多排序碼排序45如果我們把所有撲克牌排成以下次序：

2,…,A,

2,…,A,

2,…,A,

2,…,A這就是多排序碼排序。排序后形成的有序序列叫做詞典有序序列。對于上例兩排序碼的排序，可以先按花色排序，之后再按面值排序；也可以先按面值排序，再按花色排序。46如果排序碼是由多個數據項組成的數據項組，則依據它進行排序時就需要利用多排序碼排序。實現多排序碼排序有兩種常用的方法最高位優(yōu)先MSD(MostSignificantDigitfirst

)最低位優(yōu)先LSD(Least

SignificantDigitfirst)47最高位優(yōu)先MSD(MostSignificantDigitfirst

)最低位優(yōu)先LSD(Least

SignificantDigitfirst)48最低位優(yōu)先法首先依據最低位排序碼Kd對所有元素進行一趟排序，再依據次低位排序碼Kd-1對上一趟排序的結果再排序，依次重復，直到依據排序碼K1最后一趟排序完成，就可以得到一個有序的序列。49鏈式基數排序基數排序是典型的LSD排序方法,利用“分配”和“收集”對單排序碼進行排序。在這種方法中，把單排序碼Ki

看成是一個d元組：其中的每一個分量(1≤j≤d)也可看成是一個排序碼。分量有radix種取值,稱radix為基數。例如，排序碼984可以看成是一個3元組(9,8,4),每一位有0,1,…,9等10種取值，基數radix=10。50 排序碼‘data’可以看成是一個4元組(d,a,t,a),每一位有‘a’,‘b’,…,‘z’等26種取值，radix=26。針對d元組中的每一位分量,把元素序列中的所有元素,按的取值，先“分配”到rd個隊列中去。然后再按各隊列的順序，依次把元素從隊列中“收集”起來，這樣所有元素按取值排序完成。如果對于所有元素的排序碼K0,K1,…,Kn-1,依次對各位的分量,讓j=d,d-1,…,1,分別用“分配”、“收集”的運算逐趟進行排序，在最后51一趟“分配”、“收集”完成后,所有元素就按其排序碼的值從小到大排好序了。各隊列采用鏈式隊列結構,分配到同一隊列的排序碼用鏈接指針鏈接起來。每一隊列設置兩個隊列指針：intfront[radix]指示隊頭，intrear[radix]指向隊尾。為了有效地存儲和重排n個待排序元素，以靜態(tài)鏈表作為它們的存儲結構。52基數排序的“分配”與“收集”過程第一趟614921485637738101215530790306第一趟分配（按最低位i=3）re[0]re[1]re[2]re[3]re[4]re[5]re[6]