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

移動(dòng)記錄的次數(shù)，最小值為0,

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

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

現(xiàn)在，左/右子樹(shù)都已經(jīng)調(diào)整為堆，最后只要調(diào)整根結(jié)點(diǎn)，使整個(gè)二叉樹(shù)是個(gè)“堆”即可。98494064361227堆排序的時(shí)間復(fù)雜度分析：1.對(duì)深度為k的堆，“篩選”所需進(jìn)行的關(guān)鍵字比較的次數(shù)至多為2(k-1)；3.調(diào)整“堆頂”n-1

次，總共進(jìn)行的關(guān)鍵字比較的次數(shù)不超過(guò)2(

log2(n-1)

+

log2(n-2)

+…+log22)<2n(

log2n

)

因此，堆排序的時(shí)間復(fù)雜度為O(nlogn)。2.對(duì)

n

個(gè)關(guān)鍵字，建成深度為h(=

log2n+1)的堆，

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

歸并：將兩個(gè)或兩個(gè)以上的有序序列合并成一個(gè)有序序列的過(guò)程。在內(nèi)部排序中，通常采用的是2-路歸并排序。即：將兩個(gè)位置相鄰的記錄有序子序列歸并為一個(gè)記錄的有序序列。有序序列R[l..n]有序子序列R[l..m]有序子序列R[m+1..n]書(shū)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]復(fù)制到TRif(j<=n)TR[k..n]=SR[j..n];//將剩余的SR[j..n]復(fù)制到TR時(shí)間復(fù)雜度分析對(duì)n個(gè)記錄進(jìn)行歸并排序的時(shí)間復(fù)雜度為Ο(nlogn)。即：每一趟歸并的時(shí)間復(fù)雜度為O(n)，

總共需進(jìn)行

log2n

趟。6、基數(shù)排序基數(shù)排序是一種借助“多關(guān)鍵字排序”的思想來(lái)實(shí)現(xiàn)“單關(guān)鍵字排序”的內(nèi)部排序算法。6.1多關(guān)鍵字的排序6.2鏈?zhǔn)交鶖?shù)排序6.1多關(guān)鍵字的排序

n

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

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

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

例如:學(xué)生記錄含三個(gè)關(guān)鍵字:系別、班號(hào)和班內(nèi)的序列號(hào)，其中以系別為最主位關(guān)鍵字。

無(wú)序序列對(duì)K2排序?qū)1排序?qū)0排序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的排序過(guò)程如下:6.2鏈?zhǔn)交鶖?shù)排序?qū)τ跀?shù)字型或字符型的單關(guān)鍵字，可以看成是由多個(gè)數(shù)位或多個(gè)字符構(gòu)成的多關(guān)鍵字，此時(shí)可以采用這種“分配-收集”的辦法進(jìn)行排序，稱作基數(shù)排序法。例如：對(duì)下列這組關(guān)鍵字{209,386,768,185,247,606,230,834,539}首先按其“個(gè)位數(shù)”取值分別為0,1,…,9“分配”成10組，之后按從0至9的順序?qū)⑺鼈儭笆占痹谝黄?；然后按其“十位?shù)”取值分別為0,1,…,9“分配”成10組，之后再按從0至9的順序?qū)⑺鼈儭笆占痹谝黄?；最后按其“百位?shù)”重復(fù)一遍上述操作。書(shū)P287

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

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

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