第10章 內(nèi)部排序

10.1概述

10.2插入排序

10.3快速排序

10.4選擇排序

10.5歸并排序

第10章內(nèi)部排序10.1概述一、分類：內(nèi)部排序：

全部記錄都可以同時調(diào)入內(nèi)存進行的排序。外部排序：

文件中的記錄太大，無法全部將其同時調(diào)入內(nèi)存，需要多次進行內(nèi)外存交換的排序。二、定義：

設(shè)有記錄序列：{R1，R2，…，Rn}，其相應(yīng)的關(guān)鍵字序列為：{K1，K2，…，Kn};若存在一種確定的關(guān)系：Kp1<=Kp2<=

…<=Kpn

，則將記錄序列：{R1，R2，…，Rn}排成按該關(guān)鍵字有序的序列：{Rp1，Rp2，…，Rpn

}的操作，稱之為排序。

其中，關(guān)系是任意的，如通常經(jīng)常使用的小于、大于等關(guān)系。10.1概述10.1概述三、穩(wěn)定與不穩(wěn)定排序若記錄序列中的任意兩個記錄Ri、Rj

的關(guān)鍵字Ki=Kj

；如果在排序之前和排序之后，它們的相對位置保持不變，則這種排序方法是穩(wěn)定的，否則是不穩(wěn)定的。＃defineMAXSIZE20typedefintKeyType；typedefstruct{KeyTypekey;InfoTypeotherinfo;}RedType;typedefstruct{

RedTyper[MAXSIZE+1];

//r[0]空或作哨兵intlength;}SqList;四、待排記錄的數(shù)據(jù)類型－－存儲結(jié)構(gòu)見P.264

10.1概述方法：將一個記錄插入到已排好序的有序表中。初始：有序表中只有1個記錄。排序過程：每一遍，排好序的序列將增加一個元素。如果序列中有n個元素，那么最多進行n-1遍即可。10.2插入排序1.直接插入排序0123624106123456012362410612345362424i1.直接插入排序例：1061210.2插入排序70123624106123453624i1061210.2插入排序1.直接插入排序8012362410612345243624ij1061210.2插入排序1.直接插入排序9012362410612345243610i1061210.2插入排序1.直接插入排序10012362410612345243610ij61210.2插入排序1.直接插入排序11012362410612345362410ij61210.2插入排序1.直接插入排序12012362410612345362410i10j61210.2插入排序1.直接插入排序1301236241061234536246i106j1210.2插入排序1.直接插入排序14012362410612345362410i6j1210.2插入排序1.直接插入排序1501236241061234510246i36j1210.2插入排序1.直接插入排序1601236241061234536246i10j1210.2插入排序1.直接插入排序1701236241061234536246i610j1210.2插入排序1.直接插入排序1801236241061234561012i361224j10.2插入排序1.直接插入排序1901236241061234561012i3624j10.2插入排序1.直接插入排序2001236241061234561012i2436j10.2插入排序1.直接插入排序2101236241061234561012i243612j10.2插入排序1.直接插入排序2201236241063451236241210612Status

InsertSort(SqList&L){

for

(i=2;i<=L.length;++i)

if(LT(L.r[i].key,L.r[i-1].key))

{

L.r[0].key=L.r[i].key;L.r[i].key=L.r[i-1].key;

for(j=i-2;LT(L.r[0].key,L.r[j].key);--j)L.r[j+1]=L.r[j];L.r[j+1]=L.r[0];

}}//InsertSort直接插入排序算法－－P.265算法10.12310203040012345102040505030分析:移動、比較次數(shù)可作為衡量時間復(fù)雜性的標(biāo)準(zhǔn)正序時：比較次數(shù)∑1=n-1 i=2

移動次數(shù)0

n逆序時：比較次數(shù)∑

i=(n+2)(n-1)/2 i=2

移動次數(shù)∑(i+1)=(n+4)(n-1)/2 i=2nnO(n2)10.2插入排序直接插入排序算法分析：24362410612362412high1061212方法：在已排序的序列中查找下一個元素的插入位置，將該元素插入進去，形成更長的排序序列。如：12

的插入位置為下標(biāo)

3。減少了比較次數(shù)，未降低時間復(fù)雜性。ilow2.折半插入排序01234510.2插入排序25362410612362412high1061212ilow12362412high10612ilow12362412high10612ilow

m2.折半插入排序注意:找到位置時，high

指針總是指向小于待查關(guān)鍵字的那個最大關(guān)鍵字的下標(biāo)地址。

m012345退出循環(huán)后移3624121061226362410612362425high1062525ilow12362425high10625ilow1236242510625ihighlow

m

m1236242510625ihighlow2、折半插入排序注意:找到位置時，high

指針總是指向小于待查關(guān)鍵字的那個最大關(guān)鍵字的下標(biāo)地址。27StatusBInsertSort

(SqList&L){

for

(i=2;i<=L.length;++i)

{L.r[0]=L.r[i];low=1;high=i-1;

while

(low<=high){m=(low+high)/2;if(LT(L.r[0].key,L.r[m].key))

high=m-1;//L.r[0].key<L.r[m].Key左段elselow=m+1;

//L.r[0].key>=L.r[m].Key走向右段}

for(j=i-1;j>=high+1;--j)L.r[j+1]=L.r[j];//后移L.r[high+1]=L.r[0];

}}//BInsertSort折半插入排序算法－－P.267算法10.228

3.希爾排序－－縮小增量排序基本思想：

對待排記錄序列先作“宏觀”調(diào)整，再作“微觀”調(diào)整。所謂“宏觀”調(diào)整，指的是“跳躍式”的插入排序。具體做法為：

將記錄序列分成若干子序列，分別對每個子序列進行插入排序。

其中，d

稱為增量，它的值在排序過程中，從大到小逐漸縮小，直至最后一趟排序減為1。例如：將n個記錄分成d個子序列：{R[1]，R[1+d]，R[1+2d]，…，R[1+kd]}{R[2]，R[2+d]，R[2+2d]，…，R[2+kd]}…{R[d]，R[2d]，R[3d]，…，R[kd]，R[(k+1)d]}例如：1625

12

30

471123

36

9

1831

第一趟希爾排序，設(shè)增量d=51123

12

9

181625

36

30

4731

第二趟希爾排序，設(shè)增量d=3918

121123

162531

304736第三趟希爾排序，設(shè)增量d=1

911121618232530313647

1234567891011void

ShellInsert(SqList&L,int

dk){//一趟增量為dk的ShellInsert

for(i=dk+1;i<=n;++i)//對各組同時排序

if(L.r[i].key<L.r[i-dk].key)

{

L.r[0]=L.r[i];//暫存在R[0]

for(j=i-dk;j>0&&(L.r[0].key<L.r[j].key);j-=dk)L.r[j+dk]=L.r[j];//記錄后移,查找插入位置L.r[j+dk]=L.r[0];//插入

}

//if}

//P.272算法10.4void

ShellSort(SqList&L,int

dlta[],

intt){//增量為dlta[]的希爾排序

for(k=0;k<t;++t)

ShellInsert(L,dlta[k]);//調(diào)用算法10.4

//一趟增量為dlta[k]的插入排序}//－－P.272算法10.5e.g:將序列

49、38、65、97、76、13、27、49

用起泡排序的方法進行排序。0123 45678494938386565979776761313272749491.起泡排序

10.3快速排序340123 4567849384938656597977676131327274949e.g:將序列

49、38、65、97、76、13、27、49

用起泡排序的方法進行排序。

10.3快速排序1.起泡排序350123 4567849384938656597977676131327274949

10.3快速排序e.g:將序列

49、38、65、97、76、13、27、49

用起泡排序的方法進行排序。1.起泡排序360123 4567849384938656597977676131327274949

10.3快速排序e.g:將序列

49、38、65、97、76、13、27、49

用起泡排序的方法進行排序。1.起泡排序370123 4567849384938656597977676131327274949

10.3快速排序e.g:將序列

49、38、65、97、76、13、27、49

用起泡排序的方法進行排序。1.起泡排序380123 4567849384938656576977697131327274949

10.3快速排序e.g:將序列

49、38、65、97、76、13、27、49

用起泡排序的方法進行排序。1.起泡排序390123 4567849384938656576977697131327274949

10.3快速排序e.g:將序列

49、38、65、97、76、13、27、49

用起泡排序的方法進行排序。1.起泡排序400123 4567849384938656576977613971327274949

10.3快速排序e.g:將序列

49、38、65、97、76、13、27、49

用起泡排序的方法進行排序。1.起泡排序410123 4567849384938656576977613971327274949

10.3快速排序e.g:將序列

49、38、65、97、76、13、27、49

用起泡排序的方法進行排序。1.起泡排序420123 4567849384938656576977613271327974949

10.3快速排序e.g:將序列

49、38、65、97、76、13、27、49

用起泡排序的方法進行排序。1.起泡排序430123 4567849384938656576977613271327974949

10.3快速排序e.g:將序列

49、38、65、97、76、13、27、49

用起泡排序的方法進行排序。1.起泡排序440123 4567849384938656576977613271327499749

10.3快速排序e.g:將序列

49、38、65、97、76、13、27、49

用起泡排序的方法進行排序。1.起泡排序450123 45678384965761327499738496576132749973849657613274997

10.3快速排序e.g:將序列

49、38、65、97、76、13、27、49

用起泡排序的方法進行排序。1.起泡排序460123 45678384965761327499738496576132749973849657613274997

10.3快速排序e.g:將序列

49、38、65、97、76、13、27、49用起泡排序的方法進行排序。1.起泡排序470123 45678384965761327499738496576132749973849657613274997

10.3快速排序e.g:將序列

49、38、65、97、76、13、27、49

用起泡排序的方法進行排序。1.起泡排序480123 45678384965761327499738496576132749973849657613274997

10.3快速排序e.g:將序列

49、38、65、97、76、13、27、49

用起泡排序的方法進行排序。1.起泡排序490123 45678384965761327499738496576132749973849651376274997

10.3快速排序e.g:將序列

49、38、65、97、76、13、27、49

用起泡排序的方法進行排序。1.起泡排序500123 45678384965761327499738496576132749973849651376274997

10.3快速排序e.g:將序列

49、38、65、97、76、13、27、49

用起泡排序的方法進行排序。1.起泡排序510123 45678384965761327499738496576132749973849651327764997

10.3快速排序e.g:將序列

49、38、65、97、76、13、27、49

用起泡排序的方法進行排序。1.起泡排序520123 45678384965761327499738496576132749973849651327764997

10.3快速排序e.g:將序列

49、38、65、97、76、13、27、49

用起泡排序的方法進行排序。1.起泡排序530123 45678384965761327499738496576132749973849651327497697

10.3快速排序e.g:將序列

49、38、65、97、76、13、27、49

用起泡排序的方法進行排序。1.起泡排序540123 45678384965761327499713273849496576971327384949657697

10.3快速排序e.g:將序列

49、38、65、97、76、13、27、49

用起泡排序的方法進行排序。1.起泡排序550123 45678384965761327499713273849496576971327384949657697

10.3快速排序e.g:將序列

49、38、65、97、76、13、27、49

用起泡排序的方法進行排序。1.起泡排序56

0123 45678384965761327499713273849496576971327384949657697

10.3快速排序1.起泡排序結(jié)束條件：

在任何一趟進行過程中，未出現(xiàn)交換。570123 45678384965761327499713273849496576979776654949382713正序時時間復(fù)雜度：

O(n)，逆序時時間復(fù)雜度：

O(n2),平均時間復(fù)雜性O(shè)(n2)。

10.3快速排序起泡排序時間復(fù)雜性:580123 45678493838656597977676131327274949highlow49界點e.g:將序列

49、38、65、97、76、13、27、49

用快速排序的方法進行排序。2.快速排序

10.3快速排序49590123 45678493838656597977676131327274949highlow49界點2.快速排序

10.3快速排序49600123 45678493838656597977676131327274949highlow49界點2.快速排序

10.3快速排序27610123 45678493838656597977676131327274949highlow49界點2.快速排序

10.3快速排序2762493838656597977676131327274949highlow490123 45678界點2.快速排序

10.3快速排序2763493838656597977676131327274949highlow490123 45678界點2.快速排序

10.3快速排序6564493838656597977676131327274949highlow490123 45678界點2.快速排序

10.3快速排序6565493838656597977676131327274949highlow490123 45678界點2.快速排序

10.3快速排序1366493838656597977676131327274949highlow490123 45678界點2.快速排序

10.3快速排序1367493838656597977676131327274949highlow490123 45678界點2.快速排序

10.3快速排序9768493838656597977676131327274949highlow490123 45678界點2.快速排序

10.3快速排序9769493838656597977676131327274949highlow490123 45678界點2.快速排序

10.3快速排序9770493838656597977676131327274949highlow490123 45678界點2.快速排序

10.3快速排序一趟快速排序71273838136597497676139765274949highlow490123 45678界點2.快速排序

10.3快速排序2772273838136597497676139765274949highlow490123 45678界點2.快速排序

10.3快速排序1373273838136597497676139765274949highlow490123 45678界點2.快速排序

10.3快速排序13740123 45678273838136597497676139765274949highlow490123 45678界點2.快速排序

10.3快速排序3875273838136597497676139765274949highlow490123 45678界點2.快速排序

10.3快速排序2776133827386597497676139765274949highlow490123 45678界點2.快速排序

10.3快速排序76770123 45678133827386597497676139765274949highlow490123 45678界點2.快速排序

10.3快速排序4978133827386597497676139765274949highlow490123 45678界點2.快速排序

10.3快速排序49790123 45678133827386597497676139765274949highlow490123 45678界點2.快速排序

10.3快速排序9780133827386597497676139765274949highlow490123 45678界點2.快速排序

10.3快速排序9781133827386597497676139765274949highlow490123 45678界點2.快速排序

10.3快速排序6582133827386597497676139765274949highlow490123 45678界點2.快速排序

10.3快速排序6583133827386597497676139765274949highlow490123 45678界點2.快速排序

10.3快速排序7684133827386597494976136576274997highlow490123 45678界點2.快速排序

10.3快速排序4985133827386597494976136576274997highlow490123 45678界點2.快速排序

10.3快速排序49860123 45678133827386597494976136576274997highlow490123 456782.快速排序

10.3快速排序87VoidQuickSort(SqList&L)//對順序表L進行快速排序{

QSort(L,1,L.length);//調(diào)用算法10.7}//QuickSort－－P.276算法10.8

VoidQSort(SqList&L，intlow,inthigh

){if(low<high){

pivotloc=Partition(L,low,high);//P.274算法10.6(b)

Qsort(L,low,pivotloc-1);

Qsort

(L,pivotloc+1,high)}}//QSort－－P.276算法10.7快速排序算法88intPartition(SqList&L，intlow,inthigh){//P.274算法10.6(b)L.r[0]=L.r[low];pivotkey=L.r[low].key;

while(low<high)//從表的兩端交替向中間掃描

{

while(low<

high&&L.r[high].key>=

pivotkey)--high;L.r[low]=L.r[high];//low<=high

while(low

<

high

&&L.r[low].key<=pivotkey)++low;L.r[high]=L.r[low

];//low<=high

}L.r[low]=L.r[0];//low=high，樞軸記錄放到位returnlow;//返回樞軸位置}//Partition快速排序算法89VoidQuickSort(SqList&L)//對順序表L進行快速排序{

QSort(L,1,L.length);//調(diào)用算法10.7}//QuickSort－－P.276算法10.8

VoidQSort(SqList&L，intlow,inthigh

){if(low<high){

pivotloc=Partition(L,low,high);//P.274算法10.6(b)

Qsort(L,low,pivotloc-1);

Qsort

(L,pivotloc+1,high)}}//QSort－－P.276算法10.7快速排序算法90時間復(fù)雜度：快速排序在平均情況下的時間復(fù)雜性為:O(nlogn)階的。通常認為是在平均情況下最佳的排序方法。112.快速排序

10.3快速排序91

要點：對具有

n個結(jié)點的結(jié)點序列，執(zhí)行n-1

次循環(huán)。每次循環(huán)時挑出具有最大或最小關(guān)鍵字的結(jié)點。VoidSelectSort

(SqList&L)//P.277算法7.9{

for(i=1;i<L.length;++i){j=SelectMinKey(L,i);//L.r[i]~L.r[n]內(nèi)選具最小健值的下標(biāo)if(i!=j)L.r[i]<=>L.r[j];}}//SelectSort1.簡單選擇排序

10.4選擇排序92

index [0] [1] [2]

[3] [4]2410612UNSORTED1.簡單選擇排序

10.4選擇排序i=193

index [0] [1] [2]

[3] [4]6102412UNSORTEDSORTED1.簡單選擇排序

10.4選擇排序i=294

index [0] [1] [2]

[3] [4]6102412UNSORTEDSORTED1.簡單選擇排序

10.4選擇排序i=295

index [0] [1] [2]

[3] [4]6102412UNSORTEDSORTED1.簡單選擇排序

10.4選擇排序i=396

index [0] [1] [2]

[3] [4]6102412UNSORTEDSORTED1.簡單選擇排序

10.4選擇排序i=397

index [0] [1] [2]

[3] [4]6101224SORTED1.簡單選擇排序

10.4選擇排序98SelectionSort:

HowManyComparisons?3comparesforvalues[1]2comparesforvalues[2]1compareforvalues[3]=3+2+16101224

index [0] [1] [2]

[3] [4]1.簡單選擇排序

10.4選擇排序99時間復(fù)雜度含n個元素的比較次數(shù)：

Sum

=(n-1)+(n-2)+...+2+1 =O(n2

)1.簡單選擇排序

10.4選擇排序100

堆的定義：n個元素的序列{k1，k2

，……，

kn}，當(dāng)且僅當(dāng)滿足以下關(guān)系時，稱之為堆：

ki

<=

k2i

ki

>=

k2i

ki

<=

k2i+1

ki

>=

k2i+1(i=1,2,……,n/2)

且分別稱之為小頂堆和大頂堆。

e.g:序列

{96,83,27,11,9} 大頂堆

{12，36，24，85，47，30，53，91}小頂堆

或969118327231451247859136245330627318452.堆排序大頂堆小頂堆

10.4選擇排序212525*491608123456

例：關(guān)鍵字序列{21，25，49，25*，16，08}，試建大根堆。

怎樣建堆？

先將原始序列畫成完全二叉樹的形式：完全二叉樹的第一個非終端結(jié)點編號必為n/221i=3:49大于08，不必調(diào)整；i=2:

25大于25*和16，也不必調(diào)整；i=1:21小于25和49，要調(diào)整！49而且21還應(yīng)當(dāng)向下比較！！2.堆排序

10.4選擇排序08252125*1649交換1號與6號記錄492525*21160812345649252125*1608初始大頂堆2525*16211365420849例：對剛才建好的大根堆進行排序：2.堆排序

10.4選擇排序1625*21082549交換1號與5號記錄08

252125*1649從1號到5號重新調(diào)整為大頂堆082525*2116491234561625*08252149136542082525*2508

2125*1649082525*21

0816492.堆排序

10.4選擇排序08162125*2549交換1號與4號記錄25*1621082549從1號到4號重新調(diào)整為大頂堆25*1608212549123456081625*2521491365422.堆排序

10.4選擇排序08162125*2549交換1號與3號記錄21160825*2549從1號到3號重新調(diào)整為大頂堆211625*082549123456081625*2521491365422.堆排序

10.4選擇排序08162125*2549交換1號與2號記錄160821

25*2549從1號到2號重新調(diào)整為大頂堆160825*212549123456081625*2521491365422.堆排序

10.4選擇排序時間復(fù)雜性的分析：時間耗費的代價：

建堆的時間耗費＋排序的時間耗費建堆的時間耗費：

建堆的時間復(fù)雜性為4n=O(n)

級

排序的時間耗費：

T(n)=O(nlogn)

2.堆排序

10.4選擇排序108voidHeapSort(HeapType&H)//P.282算法10.11{

//對順序表H進行堆排序

for(i=H.length/2;i>0;--i)//調(diào)整為初始大頂堆

HeapAdjust(H，i,H.length);//P.282算法10.10

for

(i=H.length;

i>1;

--i){H.r[1]<=>H.r[i];

HeapAdjust

(H，1,i-1);//大頂堆的下標(biāo)為1～i-1，減少了1}}//HeapSortTypedefSqlist

HeapType;堆排序算法109Void

Heapadjust

(HeapType&H，ints,intm)//P.282算法10.10{//調(diào)整H.r[s]的關(guān)鍵字，使H.r