第十章內部排序（2）主要內容概述插入排序快速排序選擇排序歸并排序基數排序各種內部排序方法比較4、選擇排序4.1簡單選擇排序4.2堆排序4.1簡單選擇排序選擇排序的主要操作是選擇，其主要思想是：每趟排序在當前待排序序列中選出關鍵字最小的記錄，添加到有序序列中。有序序列r1r2ri-1rirnrk…………無序序列rnri+1r1r2ri-1……riri……交換最小記錄時間性能分析對n個記錄進行簡單選擇排序，所需進行的關鍵字間的比較次數總計為：

移動記錄的次數，最小值為0,

最大值為3(n-1)。4.2堆排序堆的定義:堆是具有下列性質的完全二叉樹：每個結點的值都小于或等于其左右孩子結點的值（稱為小頂堆），或每個結點的值都大于或等于其左右孩子結點的值（稱為大頂堆）。182032364525385040281.小頂堆的根結點是所有結點的最小者。2.較小結點靠近根結點，但不絕對。堆是具有下列性質的完全二叉樹：每個結點的值都小于或等于其左右孩子結點的值（稱為小頂堆），或每個結點的值都大于或等于其左右孩子結點的值（稱為大頂堆）。503845402836322018281.大頂堆的根結點是所有結點的最大者。2.較大結點靠近根結點，但不絕對。堆的定義:判斷下列二叉樹是否是堆？1236276549817355403498是堆14不首先將待排序的記錄序列構造成一個堆，此時，選出了堆中所有記錄的最小者，然后將它從堆中移走，并將剩余的記錄再調整成堆，這樣又找出了次小的記錄，以此類推，直到堆中只有一個記錄。

堆排序基本思想：1、如何“建堆”？實現堆排序，需要解決兩個問題:2、如何“篩選”？所謂“篩選”指的是，對一棵左/右子樹均為堆的完全二叉樹，“調整”根結點使整個二叉樹也成為一個堆。堆堆篩選98814973556412362740例如:是大頂堆12但在98和12進行互換之后，它就不是堆了，因此，需要對它進行“篩選”。98128173641298比較比較建堆是一個從下往上進行“篩選”的過程。40554973816436122798例如:排序之前的關鍵字序列為123681734998817355

現在，左/右子樹都已經調整為堆，最后只要調整根結點，使整個二叉樹是個“堆”即可。98494064361227堆排序的時間復雜度分析：1.對深度為k的堆，“篩選”所需進行的關鍵字比較的次數至多為2(k-1)；3.調整“堆頂”n-1

次，總共進行的關鍵字比較的次數不超過2(

log2(n-1)

+

log2(n-2)

+…+log22)<2n(

log2n

)

因此，堆排序的時間復雜度為O(nlogn)。2.對

n

個關鍵字，建成深度為h(=

log2n+1)的堆，

所需進行的關鍵字比較的次數至多4n；5、歸并排序歸并排序的主要操作是歸并，其主要思想是：將若干有序序列逐步歸并，最終得到一個有序序列。

歸并：將兩個或兩個以上的有序序列合并成一個有序序列的過程。在內部排序中，通常采用的是2-路歸并排序。即：將兩個位置相鄰的記錄有序子序列歸并為一個記錄的有序序列。有序序列R[l..n]有序子序列R[l..m]有序子序列R[m+1..n]書P283voidMerge(RcdTypeSR[],RcdType&TR[],

inti,intm,intn){

//將有序的記錄序列SR[i..m]和SR[m+1..n]//歸并為有序的記錄序列TR[i..n]}//Mergefor(j=m+1,k=i;i<=m&&j<=n;++k)

{

//將SR中記錄由小到大地并入TR

if(SR[i].key<=SR[j].key)TR[k]=SR[i++];

elseTR[k]=SR[j++];

}

……

if(i<=m)TR[k..n]=SR[i..m];//將剩余的SR[i..m]復制到TRif(j<=n)TR[k..n]=SR[j..n];//將剩余的SR[j..n]復制到TR時間復雜度分析對n個記錄進行歸并排序的時間復雜度為Ο(nlogn)。即：每一趟歸并的時間復雜度為O(n)，

總共需進行

log2n

趟。6、基數排序基數排序是一種借助“多關鍵字排序”的思想來實現“單關鍵字排序”的內部排序算法。6.1多關鍵字的排序6.2鏈式基數排序6.1多關鍵字的排序

n

個記錄的序列{R1,R2,…，Rn}對關鍵字(Ki0,Ki1,…,Kid-1)有序是指：其中:K0被稱為“最主”位關鍵字Kd-1被稱為“最次”位關鍵字對于序列中任意兩個記錄Ri和Rj(1≤i<j≤n)都滿足下列(詞典)有序關系：(Ki0,Ki1,…,Kid-1)<(Kj0,Kj1,…,Kjd-1)實現多關鍵字排序通常有兩種作法:最低位優先LSD法最高位優先MSD法

MSD法先對K0進行排序，并按K0的不同值將記錄序列分成若干子序列之后，分別對K1進行排序，...…，依次類推，直至最后對最次位關鍵字排序完成為止。

LSD法先對Kd-1進行排序，然后對Kd-2進行排序，依次類推，直至對最主位關鍵字K0排序完成為止。

例如:學生記錄含三個關鍵字:系別、班號和班內的序列號，其中以系別為最主位關鍵字。

無序序列對K2排序對K1排序對K0排序3,2,301,2,153,1,202,3,182,1,201,2,152,3,183,1,202,1,203,2,303,1,202,1,201,2,153,2,302,3,18

1,2,152,1,202,3,183,1,203,2,30LSD的排序過程如下:6.2鏈式基數排序對于數字型或字符型的單關鍵字，可以看成是由多個數位或多個字符構成的多關鍵字，此時可以采用這種“分配-收集”的辦法進行排序，稱作基數排序法。例如：對下列這組關鍵字{209,386,768,185,247,606,230,834,539}首先按其“個位數”取值分別為0,1,…,9“分配”成10組，之后按從0至9的順序將它們“收集”在一起；然后按其“十位數”取值分別為0,1,…,9“分配”成10組，之后再按從0至9的順序將它們“收集”在一起；最后按其“百位數”重復一遍上述操作。書P287

基數排序的時間復雜度為O(d(n+rd))其中：分配為O(n)

收集為O(rd)(rd為“基”)

d為“分配-收集”的趟數7、各種內部排序方法比較時間復雜度比較排序方法平均情況最好情況最壞情況直接插入排序O(n2)O(n)O(n2)希爾排序O(nlogn)O(n1.3)O(n2)起泡排序O(n2)O(n)O(n2)快速排序O(nlogn)O(nlogn)O(n2)簡單選擇排序O(n2)O(n2)O(n2)堆排序O(nlogn)O(nlogn)O(nlogn)歸并排序O(nlogn)O(nlogn)O(nlogn)基數排序O(d(n+rd)O(d(n+rd)O(d(n+rd)本章小結1、了解排序的定義和各種排序方法的特點。2、熟悉各種方法的排序過程及其依據的原則。基于“關鍵字間的比較”進行排序的方法可以按排序過程所依據的不同原則分為插入排序、交換排序、選擇排序、歸并排序和計數排序等五類。3、掌握各種排序方法的時間復雜度的分析方法。能從“關鍵字間的比較次數”分析排序算法的平均情況和最壞情況的時間性能。重點和難點：1、各種方法排序過程2、各種排序方法的時間復雜度作業：12月17日交本（一）1、給出一組關鍵字序列{29,18,25,47,58,12,51,10}。分別寫出按下列各種排序方法進行排序時的變化過程。（1）歸并排序：每歸并一次書寫一個次序。（2）快速排序：每劃分一次書寫一個次序。2、給出一組關鍵字T={12,2,16,30,8,28,4,10,20,6,18},寫出用希爾排序（第一趟排序的增量為5）從小到大排序時第一趟結束時的序列。3、選擇題：（1）對n個不同的數據元素進行冒泡排序，排序結果要求為從小到大的有序序列。在下列哪種初始情況下比較的次數最多？（）A從小到大排列好的B從大到小排列好的C元素無序