第10章排序(簡(jiǎn))詳解課件

數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容第10章排序?qū)W習(xí)要點(diǎn)理解和熟悉各種排序的基本思想和過程掌握各種排序算法的時(shí)間復(fù)雜度的分析方法和結(jié)論要求能根據(jù)各種排序方法的優(yōu)缺點(diǎn)及不同場(chǎng)合選擇合適的排序方法本章內(nèi)容10.1基本概念10.2插入排序（直接插入、折半插入、表插入排序、希爾排序）10.3快速排序（起泡排序、快速排序）10.4選擇排序（簡(jiǎn)單選擇排序、樹形選擇排序、堆排序）10.5歸并排序10.6基數(shù)排序10.7各種內(nèi)部排序方法的比較討論10.1基本概念排序（Sorting）:是將數(shù)據(jù)元素（記錄）的一個(gè)任意序列，重新排列成一個(gè)按關(guān)鍵字有序的序列。一般情況下，假設(shè)含n個(gè)記錄的序列為 （R1,R2,…,Rn）其相應(yīng)關(guān)鍵字序列為 （K1,K2,…,Kn）需確定一種排列，使關(guān)鍵字滿足如下的遞增的關(guān)系

Ki1≤Ki2≤…≤Kin

則按此關(guān)系將記錄序列重新排列為(Ri1,Ri2,…,Rin)的操作稱之為排序。學(xué)號(hào)姓名年齡性別990001王曉佳18男990002林一鵬19男990003謝寧17女990004張麗娟18女990005周濤20男990006李小燕16女關(guān)鍵字是指在一個(gè)記錄中可以標(biāo)識(shí)該數(shù)據(jù)項(xiàng)的值，它是排序運(yùn)算的重要依據(jù)。

關(guān)鍵字的選取應(yīng)根據(jù)需要而定，比如在學(xué)生檔案表中，可選擇“學(xué)號(hào)”為關(guān)鍵字來識(shí)別學(xué)生，也可選擇“年齡”為關(guān)鍵字對(duì)學(xué)生排序。9.1基本概念

按照排序過程中使用內(nèi)、外存的不同，將排序方法分為內(nèi)部排序和外部排序。內(nèi)部排序:如果待排序的記錄放在計(jì)算機(jī)內(nèi)存中進(jìn)行排序，整個(gè)排序過程不需要訪問外存便能完成，則此類排序稱為～。內(nèi)排序分類：插入排序、交換排序、選擇排序、歸并排序和基數(shù)排序。外部排序:排序的記錄數(shù)量比較大，排序期間文件的全部記錄不能同時(shí)存放在計(jì)算機(jī)的內(nèi)存里，排序過程中需要不斷地進(jìn)行內(nèi)存和外存之間的數(shù)據(jù)交換，則此類排序稱為～。排序的分類排序的目的是什么？排序算法的好壞如何衡量？時(shí)間效率——排序速度（即排序所花費(fèi)的全部比較次數(shù)）空間效率——占內(nèi)存輔助空間的大小穩(wěn)定性——若兩個(gè)記錄A和B的關(guān)鍵字值相等，但排序后A、B的先后次序保持不變，則稱這種排序算法是穩(wěn)定的。

——便于查找！10.1基本概念

在待排序的序列中，關(guān)鍵字可以是記錄的主關(guān)鍵字，也可以是記錄的次關(guān)鍵字，或是若干數(shù)據(jù)項(xiàng)的組合。由主關(guān)鍵字的定義可知，任何一個(gè)記錄的無序序列經(jīng)排序后得到的結(jié)果是唯一的。若是次關(guān)鍵字，排序的結(jié)果不唯一，因?yàn)榈却判虻挠涗浶蛄兄锌赡艽嬖趦蓚€(gè)或兩個(gè)以上關(guān)鍵字相等的記錄。若采用的排序方法使具有相同關(guān)鍵字的記錄在排序過程中相對(duì)次序不變，則稱此排序方法是穩(wěn)定的，否則稱為不穩(wěn)定的。排序的穩(wěn)定性例如：假定一組記錄為（15,67,23,15*,40），其中關(guān)鍵字同為15的記錄有兩個(gè)。如果一種排序方法使排序后的結(jié)果為（15,15*,23,40,67），則稱此方法是穩(wěn)定的；若一種排序方法使排序后的結(jié)果可能為（15*,15,23,40,67），則稱此方法是不穩(wěn)定的。

排序過程主要是對(duì)記錄的排序碼進(jìn)行比較和記錄的移動(dòng)過程。因此排序的時(shí)間復(fù)雜性可以用算法執(zhí)行中的數(shù)據(jù)比較次數(shù)及數(shù)據(jù)移動(dòng)次數(shù)來衡量。有序表與無序表 一組記錄按排序關(guān)鍵字的遞增或遞減次序排列得到的結(jié)果被稱之為有序表，相應(yīng)地，把排序前的狀態(tài)稱為無序表。正序表與逆序表 若有序表是按排序碼升序排列的，則稱為升序表或正序表，否則稱為降序表或逆序表。排序的時(shí)間復(fù)雜性#definemaxsize20 /*設(shè)記錄不超過20個(gè)*/typedef

int

KeyType; /*定義關(guān)鍵字為整數(shù)類型*/typedef

struct{

KeyTypekey;

/*關(guān)鍵字域*/

InfoType

otherinfo; /*其它數(shù)據(jù)域*/}DataType; /*記錄類型*/typedef

struct{

DataTyper[maxsize+1];/*r[0]用作監(jiān)視哨單元

*/

intlength; /*順序表長(zhǎng)度*/}SqList;

在本章討論的算法通常采用順序存儲(chǔ)結(jié)構(gòu)，用一維數(shù)組來實(shí)現(xiàn)，且記錄按照關(guān)鍵字遞增的順序排列。存儲(chǔ)結(jié)構(gòu)按排序過程中依據(jù)的不同原則對(duì)內(nèi)排方法分類：（1）插入排序（2）交換排序（3）選擇排序（4）歸并排序（5）基數(shù)排序按內(nèi)排過程中所需的工作量分類：（1）簡(jiǎn)單的排序方法，其時(shí)間復(fù)雜度為O(n×n)（2）先進(jìn)的排序方法，其時(shí)間復(fù)雜度為O(nlogn);（3）基數(shù)排序，其時(shí)間復(fù)雜度為O(d×n)排序算法的兩種基本操作：（1）比較兩個(gè)關(guān)鍵字的大??；（2）將記錄從一個(gè)位置移至另一個(gè)位置；10.2

插入排序插入排序的基本思想是：插入排序有多種具體實(shí)現(xiàn)算法：

1)直接插入排序

2)折半插入排序

3)希爾排序每步將一個(gè)待排序的對(duì)象，按其關(guān)鍵碼大小，插入到前面已經(jīng)排好序的一組對(duì)象的適當(dāng)位置上，直到對(duì)象全部插入為止。邊插入邊排序，保證子序列中隨時(shí)都是排好序的。基本思想

整個(gè)排序過程為n-1趟插入，即先將序列中第1個(gè)記錄看成是一個(gè)有序子序列，然后從第2個(gè)記錄開始，逐個(gè)進(jìn)行插入，直至整個(gè)序列有序10.2.1直接插入排序最簡(jiǎn)單的排序法！在已形成的有序表中順序查找，并在適當(dāng)位置插入，把原來位置上的元素向后順移。新元素插入到哪里？關(guān)鍵字序列T=（13，6，3，31，9，27，5，11），請(qǐng)寫出直接插入排序的中間過程序列?！?3】,6,3,31,9,27,5,11【6,13】,3,31,9,27,5,11【3,6,13】,31,9,27,5,11【3,6,13，31】,9,27,5,11【3,6,9,13，31】,27,5,11【3,6,9,13，27,31】,5,11【3,5,6,9,13，27,31】,11【3,5,6,9,11，13，27,31】

例1：基本步驟初始狀態(tài)：排序開始之前，整個(gè)數(shù)組被r分為兩個(gè)部分：有序部分和無序部分。有序部分存放的是已經(jīng)排好序的記錄；無序部分存放的是尚未排好的記錄。初始有序部分為r[1]，無序部分為r[2]到r[n]。終止?fàn)顟B(tài)：有序部分存放的是整個(gè)數(shù)組，無序部分為空?；静僮鳎好看螐臒o序部分取出一個(gè)記錄（第一個(gè)）將其同有序部分中的元素相比較，并按照關(guān)鍵字大小將其插入到合適位置，使有序部分始終有序。直至全部記錄插入完畢。直接插入排序算法描述 初值：待記錄放在無序部分的數(shù)組r[1..n]中。在有序部分中有1個(gè)元素r[1]，無序部分元素為r[2..n]；令i=2，將r[2]作為排序元素；把r[2]放到r[0]中，r[0]即作為暫存單元，又可作為后面循環(huán)比較用的“監(jiān)視哨”；取輔助參數(shù)j=i-1，其作用是記錄待比較元素的下標(biāo)（有序部分），其位置在i的前面；將r[0]的關(guān)鍵字與r[j]的關(guān)鍵字相比較；若r[0]的關(guān)鍵字小于r[j]的關(guān)鍵字，則r[j]后移一個(gè)位置，即j=j-1，然后轉(zhuǎn)向5。若r[0]的關(guān)鍵字大于r[j]的關(guān)鍵字，故r[0]應(yīng)放在r[j]的后面，即在j+1的位置。令i=i+1，若此時(shí)i>n，則排序完成，否則轉(zhuǎn)入4。關(guān)鍵字序列T=（21，25，49，25*，16，08），請(qǐng)寫出直接插入排序的具體實(shí)現(xiàn)過程。*表示后一個(gè)25i=121254925*16080123456暫存21i=2i=3i=5i=4i=625252549494925*25*49161625*080849解：假設(shè)該序列已存入一維數(shù)組r[7]中，將r[0]作為監(jiān)視哨。則程序執(zhí)行過程為：21254925*21初態(tài)：164925*25211608完成!例2：10.2.1直接插入排序直接插入排序算法(P265)voidInsertSort(SqList&S){

for(i=2;i<=S.length;++i)

if(S.r[i].key<S.r[i-1].key){

//否則無需到有序序列中比較

S.r[0]=S.r[i];

for(j=i-1;S.r[0].key<S.r[j].key;--j)

S.r[j+1]=S.r[j];

S.r[j+1]=S.r[0];

}}直接插入排序的性能分析:—穩(wěn)定排序方法(1)空間:只需一個(gè)記錄的輔助空間r[0]，S(n)=O(1).(2)時(shí)間:

基本運(yùn)算:比較和移動(dòng)記錄;比較和移動(dòng)記錄的次數(shù)與關(guān)鍵字的初始序列有關(guān):(1)待排序序列關(guān)鍵字正序排序(最優(yōu)):

關(guān)鍵字比較次數(shù):n-1

移動(dòng)記錄的次數(shù):0(2)待排序序列關(guān)鍵字逆序排序（最差）:

關(guān)鍵字比較次數(shù):2+3+…+n=(n+2)(n-1)/2

移動(dòng)記錄的次數(shù):3+4+5+…+(n+1)=(n+4)(n-1)/2(3)待排序序列關(guān)鍵字隨機(jī)排序（平均）:

關(guān)鍵字比較次數(shù):(n-1)(n+2)/4

移動(dòng)記錄的次數(shù):(n+4)(n-1)/4直接插入排序算法的時(shí)間復(fù)雜度為O(n×n)優(yōu)點(diǎn)：比較的次數(shù)大大減少，全部元素比較次數(shù)僅為O(nlog2n)。時(shí)間效率：雖然比較次數(shù)大大減少，可惜移動(dòng)次數(shù)并未減少，所以排序時(shí)間效率仍為O(n2)

。空間效率：只需一個(gè)記錄的輔助空間r[0]，即為O（1）穩(wěn)定性：穩(wěn)定

新元素插入到哪里？

在已形成的有序表中折半查找，并在適當(dāng)位置插入，把原來位置上的元素向后順移。10.2.2折半插入排序（P266）用折半查找方法確定插入位置的排序叫～例i=1(30)1370853942620i=213(1330)70853942620i=76(6133039427085)20…...i=820(6133039427085)20lowhighmi=820(6133039427085)20lowhighmi=820(6133039427085)20lhighmi=820(6133039427085)20lowhighi=820(613203039427085)當(dāng)high>low時(shí)查找結(jié)束，插入的位置為high所指位置的后一個(gè)位置討論：若記錄是鏈表結(jié)構(gòu)，用直接插入排序行否？折半插入排序呢？答：直接插入不僅可行，而且還無需移動(dòng)元素，時(shí)間效率更高！但鏈表無法“折半查找”！10.2.3希爾排序(縮小增量法)希爾排序方法又稱為“縮小增量”排序基本思想

先將整個(gè)待排序的記錄序列分割為若干個(gè)子序列并分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄“基本有序”時(shí)，再對(duì)全體記錄進(jìn)行一次直接插入排序。

技巧：子序列的構(gòu)成不是簡(jiǎn)單地“逐段分割”，而是將相隔某個(gè)增量dk的記錄組成一個(gè)子序列,讓增量dk逐趟縮短（例如依次取5,3,1），直到dk＝1為止。優(yōu)點(diǎn)：讓關(guān)鍵字值小的元素能跳躍式地前移，而不是一步一步的前移，且序列若基本有序時(shí)，再用直接插入排序處理，時(shí)間效率會(huì)高很多。38例：關(guān)鍵字序列T=(49，38，65，97,76,13,27,49*，55,04），請(qǐng)寫出希爾排序的具體實(shí)現(xiàn)過程。0123456789104938659776132749*5504初態(tài)：第1趟(dk=5)第2趟(dk=3)第3趟(dk=1)4913134938276549*9755760427386549*9755135576045513270427044949*4949*76387665659797551327044949*3876659713270449*7697算法分析：開始時(shí)dk

的值較大，子序列中的對(duì)象較少，排序速度較快；隨著排序進(jìn)展，dk

值逐漸變小，子序列中對(duì)象個(gè)數(shù)逐漸變多，由于前面工作的基礎(chǔ)，大多數(shù)對(duì)象已基本有序，所以排序速度仍然很快。r[i]排序過程：先取一個(gè)正整數(shù)d1<n，把所有相隔d1的記錄放一組，組內(nèi)進(jìn)行直接插入排序；然后取d2<d1，重復(fù)上述分組和排序操作；直至di=1，即所有記錄放進(jìn)一個(gè)組中排序?yàn)橹估纾簩個(gè)記錄分成d個(gè)子序列：

{R[1]，R[1+d1]，R[1+2d1]，…，R[1+kd1]}{R[2]，R[2+d1]，R[2+2d1]，…，R[2+kd1]}…{R[d1]，R[2d1]，R[3d1]，…，R[kd1]，R[(k+1)d1]}希爾排序特點(diǎn)子序列的構(gòu)成不是簡(jiǎn)單的“逐段分割”，而是將相隔某個(gè)增量的記錄組成一個(gè)子序列希爾排序可提高排序速度，因?yàn)榉纸M后n值減小，n2更小，而T(n)=O(n2),所以T(n)從總體上看是減小了關(guān)鍵字較小的記錄跳躍式前移，在進(jìn)行最后一趟增量為1的插入排序時(shí)，序列已基本有序增量序列取法沒有除1以外的公因子最后一個(gè)增量值必須為1算法分析時(shí)間復(fù)雜度 希爾排序算法的速度是所取的增量序列di的函數(shù)。增量序列的選取是一件困難的事。一般認(rèn)為，希爾排序的時(shí)間復(fù)雜度為O(nlog2n)。空間復(fù)雜度

空間復(fù)雜度為O(1)。

穩(wěn)定性

由于shell排序是分組進(jìn)行排序，它是跳躍式向前移動(dòng)，會(huì)導(dǎo)致相等關(guān)鍵字中原來在后面的關(guān)鍵字移到前面，所以希爾排序是不穩(wěn)定的排序方法。課堂練習(xí)：1.

欲將序列（Q,H,C,Y,P,A,M,S,R,D,F,X）中的關(guān)鍵碼按字母升序重排，則初始步長(zhǎng)為4的希爾排序一趟的結(jié)果是？答：原始序列：Q,H,C,Y,P,A,M,S,R,D,F,X

shell一趟后：2.直接插入排序和希爾排序，哪個(gè)易于在鏈表（包括各種單、雙、循環(huán)鏈表）上實(shí)現(xiàn)？P,Q,R,A,D,H,C,F,M,S,X,Y答：直接插入排序方法易于在鏈表上實(shí)現(xiàn)；希爾排序方法因?yàn)槭前丛隽窟x擇記錄，不易于在鏈表上實(shí)現(xiàn)。10.3交換排序兩兩比較待排序記錄的關(guān)鍵碼，如果發(fā)生逆序（即排列順序與排序后的次序正好相反），則交換之，直到所有記錄都排好序?yàn)橹?。交換排序的主要算法有：

1)冒泡排序

2)快速排序交換排序的基本思想是：基本思想

每趟不斷將記錄兩兩比較，并按“前小后大”規(guī)則交換。使得關(guān)鍵字較小的元素逐漸從后部移向前部（從下標(biāo)較大的單元移向下標(biāo)較小的單元），就象水底下的氣泡一樣逐漸向上冒。10.3.1冒泡排序—穩(wěn)定排序優(yōu)點(diǎn)：

每趟結(jié)束時(shí)，不僅能擠出一個(gè)最大值到最后面位置，還能同時(shí)部分理順其他元素；一旦某趟沒有交換發(fā)生，還可以提前結(jié)束排序。因?yàn)榕判虻倪^程中，各元素不斷接近自己的位置，如果一趟比較下來沒有進(jìn)行過交換，就說明序列有序，因此要在排序過程中設(shè)置一個(gè)標(biāo)志flag判斷元素是否進(jìn)行過交換。從而減少不必要的比較。前提：順序存儲(chǔ)結(jié)構(gòu)

將第一個(gè)記錄的關(guān)鍵字與第二個(gè)記錄的關(guān)鍵字進(jìn)行比較，若為逆序r[1].key>r[2].key，則交換；然后比較第二個(gè)記錄與第三個(gè)記錄；依次類推，直至第n-1個(gè)記錄和第n個(gè)記錄比較為止——第一趟冒泡排序，結(jié)果關(guān)鍵字最大的記錄被安置在最后一個(gè)記錄上；

對(duì)前n-1個(gè)記錄進(jìn)行第二趟冒泡排序，結(jié)果使關(guān)鍵字次大的記錄被安置在第n-1個(gè)記錄位置；

重復(fù)上述過程，直到“在一趟排序過程中沒有進(jìn)行過交換記錄的操作”為止。排序過程例49

38

65

97

76

13

27

30

初始關(guān)鍵字38

49

65

76

13

27

30

97第一趟38

49

65

13

27

30

76第二趟38

49

13

27

30

65

第三趟38

13

27

30

49

第四趟13

27

30

38第五趟13

27

30

第六趟38497697139727973097137676762730136527653065131349493049273827383038冒泡排序算法voidBubbleSort(SqList&S){

for(i=1;i<=n-1;i++){ /*做n-1趟排序*/

noswap=true;

/*置未交換的標(biāo)志*/

for(j=1;j<=n-i+1;j++) /*從前往后掃描*/

if(S.r[j].key>S.r[j+1].key){

/*交換記錄*/

temp=S.r[j+1];

S.r[j+1]=S.r[j];

S.r[j]=temp;

noswap=false;

}

if(noswap)

return;

/*本趟排序未發(fā)生交換,終止算法*/

}}起泡排序算法的性能分析:(1)空間:只需一個(gè)記錄的輔助空間.(2)時(shí)間:

基本運(yùn)算:比較和移動(dòng)記錄;比較和移動(dòng)記錄的次數(shù)與關(guān)鍵字的初始序列有關(guān):(1)待排序序列關(guān)鍵字正序排序（最好）:

關(guān)鍵字比較次數(shù):n-1

移動(dòng)記錄的次數(shù):0(2)待排序序列關(guān)鍵字逆序排序（最壞）:

關(guān)鍵字比較次數(shù):(n-1)+(n-2)+…+1=n(n-1)/2

移動(dòng)記錄的次數(shù):3n(n-1)/2(3)待排序序列關(guān)鍵字隨機(jī)排序（平均）:

關(guān)鍵字比較次數(shù):(n-1)n/4

移動(dòng)記錄的次數(shù):3n(n-1)/4起泡排序算法的時(shí)間復(fù)雜度為O(n×n)改進(jìn)的著眼點(diǎn)：在起泡排序中，記錄的比較和移動(dòng)是在相鄰單元中進(jìn)行的，記錄每次交換只能上移或下移一個(gè)單元，因而總的比較次數(shù)和移動(dòng)次數(shù)較多。交換排序減少總的比較次數(shù)和移動(dòng)次數(shù)增大記錄的比較和移動(dòng)距離較大記錄從前面直接移動(dòng)到后面較小記錄從后面直接移動(dòng)到前面10.3.2快速排序10.3.2快速排序從待排序列中任取一個(gè)元素(例如取第一個(gè))作為中心，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右兩個(gè)子表；然后再對(duì)各子表重新選擇中心元素并依此規(guī)則調(diào)整，直到每個(gè)子表的元素只剩一個(gè)。此時(shí)便為有序序列了?；舅枷耄簝?yōu)點(diǎn)：因?yàn)槊刻丝梢源_定不止一個(gè)元素的位置，而且呈指數(shù)增加，所以特別快！前提：順序存儲(chǔ)結(jié)構(gòu)

選擇樞軸的方法：1.使用第一個(gè)記錄的關(guān)鍵碼；2.選取序列中間記錄的關(guān)鍵碼；3.比較序列中第一個(gè)記錄、最后一個(gè)記錄和中間記錄的關(guān)鍵碼，取關(guān)鍵碼居中的作為軸值并調(diào)換到第一個(gè)記錄的位置；4.隨機(jī)選取軸值。關(guān)鍵問題⑴：如何選擇軸值？選取不同樞軸的后果：決定兩個(gè)子序列的長(zhǎng)度，子序列的長(zhǎng)度最好相等。排序過程：對(duì)r[s……t]中記錄進(jìn)行一趟快速排序，附設(shè)兩個(gè)指針i和j，設(shè)樞軸記錄rp=r[s]，x=rp.key初始時(shí)令i=s,j=t首先從j所指位置向前搜索第一個(gè)關(guān)鍵字小于x的記錄，并和rp交換再?gòu)膇所指位置起向后搜索，找到第一個(gè)關(guān)鍵字大于x的記錄，和rp交換重復(fù)上述兩步，直至i==j為止，便是樞軸記錄r[s]的最終位置。再分別對(duì)兩個(gè)子序列進(jìn)行快速排序，直到每個(gè)子序列只含有一個(gè)記錄為止例初始關(guān)鍵字：4938659776132750ijxji完成一趟排序：(273813)49(76976550)分別進(jìn)行快速排序：(13)27(38)49(5065)76(97)快速排序結(jié)束：13273849

506576974927ijijij4965ji1349ij4997ijLow=high=3，本趟停止，將樞軸定位并返回位置信息關(guān)鍵字序列T=(21，25，49，25*，16，08），請(qǐng)寫出快速排序算法的一趟實(shí)現(xiàn)過程。r[i]0123456初態(tài)21254925*1608第1趟highlow210825164925*321r[0]=2108251649(08

，16）21

（25*，49，25）25*跑到了前面，不穩(wěn)定！例：lowhighhighlowhigh例3：以關(guān)鍵字序列（256，301，751，129，937，863，742，694，076，438）為例，寫出執(zhí)行快速算法的各趟排序結(jié)束時(shí)，關(guān)鍵字序列的狀態(tài)。原始序列：

256，301，751，129，937，863，742，694，076，438快速排序第1趟第2趟第3趟第4趟256，301，751，129，937，863，742，694，076，438076，129，256，751，937，863，742，694，301，438256076301129751256076，129，256，438，301，694，742，694，863，937751076，129，256，438，301，694，742，751，863，937076，129，256，301，301，694，742，751，863，937438076，129，256，301，438，694，742，751，863，937例：{38,27,55,50,13,49,65}的快速排序遞歸樹如下：38135055496527快速排序的遞歸執(zhí)行過程可以用遞歸樹描述。算法評(píng)價(jià)從快速排序算法的遞歸樹可知，快速排序的趟數(shù)取決于遞歸樹的深度。如果每次劃分對(duì)一個(gè)對(duì)象定位后，該對(duì)象的左側(cè)子序列與右側(cè)子序列的長(zhǎng)度相同，則下一步將是對(duì)兩個(gè)長(zhǎng)度減半的子序列進(jìn)行排序，這是最理想的情況。算法評(píng)價(jià)時(shí)間復(fù)雜度最好情況（每次總是選到中間值作樞軸）T(n)=O(nlog2n)最壞情況（每次總是選到最小或最大元素作樞軸）T(n)=O(n2)平均時(shí)間復(fù)雜度為O（nlog2n）空間復(fù)雜度：需?？臻g以實(shí)現(xiàn)遞歸最壞情況：S(n)=O(n)一般情況：S(n)=O(log2n)穩(wěn)定性：快速排序是不穩(wěn)定排序。目前同數(shù)量級(jí)O（nlog2n）中最快的內(nèi)部排序方法10.4選擇排序基本思想

在待排記錄中依次選擇關(guān)鍵字最小的記錄添加到有序序列中，逐漸縮小范圍直至全部記錄選擇完畢。選擇排序的主要算法有：

1)簡(jiǎn)單選擇排序

2)堆排序10.4.1簡(jiǎn)單選擇排序（直接選擇排序）基本思想

每一趟從待排的無序區(qū)中選出關(guān)鍵字最小的記錄，順序放在已排好序的子序列的最后，直至記錄全部排完。具體步驟首先在無序區(qū)R[1..n]中選出關(guān)鍵字最小的記錄，將它與R[1]交換；然后在無序區(qū)R[2..n]中選出關(guān)鍵字最小的記錄，將它與R[2]交換。重復(fù)此過程。當(dāng)?shù)趇趟排序時(shí)R[1..i-1]已是有序區(qū)，從無序區(qū)R[i..n]中選出關(guān)鍵字最小的記錄R[k]，將它與R[i]交換，使R[1..i]為有序區(qū)?？梢姡麄€(gè)過程需要n-1趟排序。

例初始：[49386597761327]minjjjjjjminmini=11349一趟：13[386597764927]i=2minminjjjjj2738二趟：1327[6597764938]三趟：132738[97764965]四趟：13273849[769765]五趟：1327384965[9776]六趟：132738496576[97]排序結(jié)束：13273849657697簡(jiǎn)單選擇排序的算法設(shè)計(jì):(1)需進(jìn)行n-1趟選擇操作;(2)第i趟選擇操作為:通過n-i次關(guān)鍵字間比較,從n-i+1個(gè)記錄中選出關(guān)鍵字最小的記錄,并和第i個(gè)記錄交換;簡(jiǎn)單選擇排序算法voidSelectSort(SqList

&S){

/*對(duì)r[1..n]進(jìn)行簡(jiǎn)單選擇排序*/

for(i=1;i<S.length;++i){ /*做n-1趟排序*/

min=i;

/*min記錄最小元素下標(biāo)*/

for(j=i+1;j<=S.length;j++)

/*在當(dāng)前無序區(qū)S.r[i..n]中選關(guān)鍵字最小的記錄S.r[min]*/

if(S.r[j].key<S.r[min].key)

min=j;

if(min!=i){

/*交換R[i]和R[min]*/

temp=S.r[i];

S.r[i]=S.r[min];

S.r[min]=temp;

}

}}簡(jiǎn)單選擇排序算法分析時(shí)間復(fù)雜度記錄移動(dòng)次數(shù)最好情況（正序）：0最壞情況（逆序）：3(n-1)平均:[0+3(n-1)]/2=3(n-1)/2比較次數(shù)： 整個(gè)排序過程共需n-1趟比較，在第i趟中需比較n-i次，故總比較次數(shù)為：故直接選擇排序的時(shí)間復(fù)雜度為O（n2）?？臻g復(fù)雜度

O（1）穩(wěn)定性

不穩(wěn)定的排序方法10.4.2堆排序堆的概念 設(shè)有n個(gè)元素的序列

k1，k2，…，kn，當(dāng)且僅當(dāng)滿足下述關(guān)系之一時(shí)，稱之為堆。

Ki≤K2i和Ki≤K2i+1

或Ki≥K2i和Ki≥K2i+1

其中，K1必是數(shù)列中的最大值或最小值，可分別成為大根堆（二叉樹的所有根結(jié)點(diǎn)值大于或等于左右孩子的值）和小根堆（二叉樹的所有根結(jié)點(diǎn)值小于或等于左右孩子的值）。下圖是兩種堆的示例。2412473885913053859136

4724165330大根堆 小根堆10.4.2堆排序16

9

810

6

2

11

1

5

4不是堆基本思想

堆排序（HeapSort）是對(duì)選擇排序的一種改進(jìn)方法，屬于樹形排序法。在排序過程中，將R[1..n]看成是一棵完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)，利用雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)間的內(nèi)在關(guān)系來選擇關(guān)鍵字最小的記錄。堆排序——若在輸出堆頂元素之后，使得剩余n-1個(gè)元素的序列重又建成一個(gè)堆，則得到n個(gè)元素中的次小值。如此反復(fù)執(zhí)行，便能得到一個(gè)有序序列，這個(gè)過程稱之為堆排序。10.4.2堆排序排序過程（小根堆）

⑴

以初始關(guān)鍵字序列，建立堆；

⑵輸出堆頂最小元素；

⑶調(diào)整余下的元素，使其成為一個(gè)新堆；

⑷重復(fù)⑵,⑶n次，得到一個(gè)有序序列。實(shí)現(xiàn)堆排序關(guān)鍵要解決⑴和⑶兩個(gè)問題：

一、如何由一個(gè)無序序列建成一個(gè)堆?二、輸出堆頂元素后，如何調(diào)整余下的元素成為一個(gè)新堆?10.4.2堆排序問題二的解決方案：輸出堆頂元素后，堆的重建： 解決這一問題可采用“篩選法”。篩選法的基本思想為：設(shè)有n個(gè)元素的堆，輸出堆頂元素后，剩下n-1個(gè)元素。將堆底（堆中最后一個(gè)元素）推向堆頂。然后將根結(jié)點(diǎn)值與左、右子樹的根結(jié)點(diǎn)值進(jìn)行比較，并將它與其中小者進(jìn)行交換；重復(fù)上述操作，直至葉子結(jié)點(diǎn)，將得到新的堆，稱這個(gè)從堆頂至葉子的調(diào)整過程為“篩選”。2412473885913053249147388530539124473885305330244738859153a.輸出堆頂12，將堆低91送入堆頂b.堆被破壞，根結(jié)點(diǎn)與右孩子交換c.右子樹不滿足堆，其根與左孩子交換d.堆已重建成堆重建示例初始建堆問題一的解決方案：n個(gè)記錄初始建堆的過程：對(duì)初始序列建堆的過程，就是一個(gè)反復(fù)進(jìn)行“篩選”的過程。（1）將此無序序列看成是一個(gè)完全二叉樹，則最后一個(gè)非葉子結(jié)點(diǎn)是第|n/2|個(gè)元素。（2）依次對(duì)第|n/2|，|n/2|-1,|n/2|-2,…,1個(gè)元素進(jìn)行篩選。例

含8個(gè)元素的無序序列（49，38，65，97，76，13，27，50）4950`653827137697初始完全二叉樹下面對(duì)第4、3、2、1個(gè)元素進(jìn)行篩選，使其成為一個(gè)小根堆例含8個(gè)元素的無序序列（49，38，65，97，76，13，27，50）4965382713769750496538271376509749133827657650974913382765765097132738496576509712345678493865977613275050971365381327494913382765765097對(duì)97進(jìn)行篩選對(duì)65進(jìn)行篩選對(duì)38進(jìn)行篩選對(duì)49進(jìn)行篩選最后得到的小根堆例:對(duì)關(guān)鍵字序列{49,38,65,97,76,13,27,50}進(jìn)行堆排序13273849657650979727384965765013輸出：132749389765765013輸出：139749382765765013輸出：13273849502765769713輸出：13276549502738769713輸出：132738堆排序示例4965502738769713輸出：1327387665502738499713輸出：132738495065762738499713輸出：132738499765762738495013輸出：13273849506597762738495013輸出：13273849509765762738495013輸出：1327384950657665972738495013輸出：1327384950659765762738495013輸出：132738495065769765762738495013輸出：1327384950657697堆排序算法分析算法評(píng)價(jià)時(shí)間復(fù)雜度：最壞情況下T(n)=O(nlog2n)空間復(fù)雜度：S(n)=O(1)堆排序的性能堆排序是不穩(wěn)定的；堆排序適用于n較大的情況10.5歸并排序法歸并排序

所謂歸并就是將兩個(gè)或兩個(gè)以上的有序表合并成一個(gè)有序表。歸并的基本操作是將兩個(gè)位置相鄰的有序記錄子序列R[i..m]和R[m+1..n]歸并成一個(gè)有序記錄序列R[i..n]?；舅枷?/p>

將記錄序列R[1..n]看成是n個(gè)長(zhǎng)度為1的子序列，然后兩兩歸并，得到┏n/2┓個(gè)長(zhǎng)度為2或1的有序子序列。再兩兩歸并，重復(fù)此過程，直至得到一個(gè)長(zhǎng)度為n的有序序列為止。這種方法每次都將兩個(gè)序列合并成一個(gè)序列，故稱為2路歸并排序。例初始關(guān)鍵字：[49][38][65][97][76][13][27]一趟歸并后：[3849][6597][1376][27]二趟歸并后：[38496597][132776]三趟歸并后：[13273849657697]10.5歸并排序法要解決的關(guān)鍵問題：如何將兩個(gè)有序表歸并為一個(gè)有序表？其基本思想是：設(shè)兩個(gè)有序表A和B的對(duì)象個(gè)數(shù)(表長(zhǎng))分別為al

和bl，變量i

和j

分別是表A和表B的當(dāng)前檢測(cè)指針。設(shè)表C是歸并后的新有序表，變量k

是它的當(dāng)前存放指針。08212525*49627293163754lmm+1ninitListij0816212525*374954627293lnkmergeList當(dāng)i

和j

都在兩個(gè)表的表長(zhǎng)內(nèi)變化時(shí)，根據(jù)A[i]與B[j]的關(guān)鍵字的大小，依次把關(guān)鍵字小的對(duì)象排放到新表C[k]中；當(dāng)i

與j中有一個(gè)已經(jīng)超出表長(zhǎng)時(shí)，將另一個(gè)表中的剩余部分照抄到新表C[k]中。C表A表B表

將下面兩個(gè)已排序的順序表合并成一個(gè)有序表。順序比較兩者的相應(yīng)元素，小者移入另一表中，反復(fù)如此，直至其中任一表都移入另一表為止。4913659776780AB

0

1234567Cijk

01234674913659776780ABCijk7

0

1234567

01234684913659776780ABCijk7

0

1234567

01234694913659776780ABCijk713

0

1234567

01234704913659776780ABCijk71349

0

1234567

01234714913659776780ABCijk71349

0

1234567

01234724913659776780ABCijk7134965

0

1234567

01234734913659776780ABCijk7134965

0

1234567

01234744913659776780ABCijk713496576

0

1234567

01234754913659776780ABCijk713496576

0

1234567

01234764913659776780ABCijk71349657680

0

1234567

01234774913659776780ABCijk71349657680

0

1234567

01234784913659776780ABCijk71349657680至此B表的元素都已移入C表，只需將A表的剩余部分移入C表即可。

0

1234567

0123479

012344913659776780ABCijk71349657680至此B表的元素都已移入C表，只需將A表的剩余部分移入C表即可。97

0

123456780歸并排序算法voidMerge(DataType

S[],DataType

T[],int

i,int

m,intn){/*將有序的S[i..m]和S[m+1..n]歸并為有序的T[i..n]*/ for(j=m+1,k=i;i<=m&&j<=n;++k) {/*將S中記錄由小到大地并入T*/ if(S[i].key<=S[j].key)T[k]=S[i++]; elseT[k]=S[j++]; } while(i<=m)

T[k++]=S[i++];/*將剩余的S[i..m]復(fù)制到T*/ while(j<=n)

T[k++]=S[j++];/*將剩余的S[j..n]復(fù)制到T*/}10.5歸并排序法歸并排序

歸并排序在算法實(shí)現(xiàn)時(shí)，可先將待排序列R[s..t]分成兩塊：R[s..（s+t）/2]和R[（s+t）/2+1..t]。分別對(duì)兩個(gè)子序列進(jìn)行歸并排序，最后對(duì)記錄實(shí)施歸并操作，使R[s..t]成為有序序列。

voidMsort(DataType

S[],DataTypeT1[],ints,intt){ if(s==t)T1[s]=S[s]; else{ m=(s+t)/2;//將S[s..t]平分為S[s..m]和S[m+1..t]

Msort(S,T2,s,m);

Msort(S,T2,m+1,t); Merge(T2,T1,s,m,t); }}10.5歸并排序法算法評(píng)價(jià)一趟歸并操作是將r[1]~r[n]中相鄰的長(zhǎng)度為h的有序序列進(jìn)行兩兩歸并，并把結(jié)果存放到r1[1]~r1[n]中，這需要O(n)時(shí)間。整個(gè)歸并排序需要進(jìn)行「

log2n

」趟，因此，總的時(shí)間代價(jià)是O(nlog2n)。時(shí)間復(fù)雜度：T(n)=O(nlog2n)空間