第10章 内部排序

10.1概述

10.2插入排序

10.3快速排序

10.4选择排序

10.5归并排序

第10章内部排序10.1概述一、分类：内部排序：

全部记录都可以同时调入内存进行的排序。外部排序：

文件中的记录太大，无法全部将其同时调入内存，需要多次进行内外存交换的排序。二、定义：

设有记录序列：{R1，R2，…，Rn}，其相应的关键字序列为：{K1，K2，…，Kn};若存在一种确定的关系：Kp1<=Kp2<=

…<=Kpn

，则将记录序列：{R1，R2，…，Rn}排成按该关键字有序的序列：{Rp1，Rp2，…，Rpn

}的操作，称之为排序。

其中，关系是任意的，如通常经常使用的小于、大于等关系。10.1概述10.1概述三、稳定与不稳定排序若记录序列中的任意两个记录Ri、Rj

的关键字Ki=Kj

；如果在排序之前和排序之后，它们的相对位置保持不变，则这种排序方法是稳定的，否则是不稳定的。＃defineMAXSIZE20typedefintKeyType；typedefstruct{KeyTypekey;InfoTypeotherinfo;}RedType;typedefstruct{

RedTyper[MAXSIZE+1];

//r[0]空或作哨兵intlength;}SqList;四、待排记录的数据类型－－存储结构见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分析:移动、比较次数可作为衡量时间复杂性的标准正序时：比较次数∑1=n-1 i=2

移动次数0

n逆序时：比较次数∑

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

移动次数∑(i+1)=(n+4)(n-1)/2 i=2nnO(n2)10.2插入排序直接插入排序算法分析：24362410612362412high1061212方法：在已排序的序列中查找下一个元素的插入位置，将该元素插入进去，形成更长的排序序列。如：12

的插入位置为下标

3。减少了比较次数，未降低时间复杂性。ilow2.折半插入排序01234510.2插入排序25362410612362412high1061212ilow12362412high10612ilow12362412high10612ilow

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

指针总是指向小于待查关键字的那个最大关键字的下标地址。

m012345退出循环后移3624121061226362410612362425high1062525ilow12362425high10625ilow1236242510625ihighlow

m

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

指针总是指向小于待查关键字的那个最大关键字的下标地址。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.希尔排序－－缩小增量排序基本思想：

对待排记录序列先作“宏观”调整，再作“微观”调整。所谓“宏观”调整，指的是“跳跃式”的插入排序。具体做法为：

将记录序列分成若干子序列，分别对每个子序列进行插入排序。

其中，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

第一趟希尔排序，设增量d=51123

12

9

181625

36

30

4731

第二趟希尔排序，设增量d=3918

121123

162531

304736第三趟希尔排序，设增量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]);//调用算法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.起泡排序结束条件：

在任何一趟进行过程中，未出现交换。570123 45678384965761327499713273849496576979776654949382713正序时时间复杂度：

O(n)，逆序时时间复杂度：

O(n2),平均时间复杂性O(n2)。

10.3快速排序起泡排序时间复杂性: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);//调用算法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);//调用算法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时间复杂度：快速排序在平均情况下的时间复杂性为:O(nlogn)阶的。通常认为是在平均情况下最佳的排序方法。112.快速排序

10.3快速排序91

要点：对具有

n个结点的结点序列，执行n-1

次循环。每次循环时挑出具有最大或最小关键字的结点。VoidSelectSort

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

for(i=1;i<L.length;++i){j=SelectMinKey(L,i);//L.r[i]~L.r[n]内选具最小健值的下标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时间复杂度含n个元素的比较次数：

Sum

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

)1.简单选择排序

10.4选择排序100

堆的定义：n个元素的序列{k1，k2

，……，

kn}，当且仅当满足以下关系时，称之为堆：

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

例：关键字序列{21，25，49，25*，16，08}，试建大根堆。

怎样建堆？

先将原始序列画成完全二叉树的形式：完全二叉树的第一个非终端结点编号必为n/221i=3:49大于08，不必调整；i=2:

25大于25*和16，也不必调整；i=1:21小于25和49，要调整！49而且21还应当向下比较！！2.堆排序

10.4选择排序08252125*1649交换1号与6号记录492525*21160812345649252125*1608初始大顶堆2525*16211365420849例：对刚才建好的大根堆进行排序：2.堆排序

10.4选择排序1625*21082549交换1号与5号记录08

252125*1649从1号到5号重新调整为大顶堆082525*2116491234561625*08252149136542082525*2508

2125*1649082525*21

0816492.堆排序

10.4选择排序08162125*2549交换1号与4号记录25*1621082549从1号到4号重新调整为大顶堆25*1608212549123456081625*2521491365422.堆排序

10.4选择排序08162125*2549交换1号与3号记录21160825*2549从1号到3号重新调整为大顶堆211625*082549123456081625*2521491365422.堆排序

10.4选择排序08162125*2549交换1号与2号记录160821

25*2549从1号到2号重新调整为大顶堆160825*212549123456081625*2521491365422.堆排序

10.4选择排序时间复杂性的分析：时间耗费的代价：

建堆的时间耗费＋排序的时间耗费建堆的时间耗费：

建堆的时间复杂性为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)//调整为初始大顶堆

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);//大顶堆的下标为1～i-1，减少了1}}//HeapSortTypedefSqlist

HeapType;堆排序算法109Void

Heapadjust

(HeapType&H，ints,intm)//P.282算法10.10{//调整H.r[s]的关键字，使H.r