中山大学-数据结构-内部排序

第十章内部排序学习目标理解排序的定义和各种排序方法的特点，并能加以灵活应用。排序方法有不同的分类方法，基于“关键字间的比较”进行排序的方法可以按排序过程所依据的不同原则分为插入排序、快速（交换）排序、选择排序、归并排序和基数排序等五类。掌握各种排序方法的时间复杂度的分析方法。能从“关键字间的比较次数”分析排序算法的平均情况和最坏情况的时间性能。按平均时间复杂度划分，内部排序可分为三类：O(n2)的简单排序方法，O(n·logn)的高效排序方法和O(d·n)的基数排序方法。理解排序方法“稳定”或“不稳定”的含义。2/3/20231重点和难点重点：希尔排序、快速排序、堆排序和归并排序等高效方法难点：希尔排序、快速排序、堆排序和归并排序等高效方法知识点排序、直接插入排序、折半插入排序、表插入排序、希尔排序、起泡排序、快速排序、简单选择排序、堆排序、2-路归并排序、基数排序、排序方法的综合比较。2/3/2023210.1概述排序假设含有n个记录的序列为：{R1，R2，…，Rn}，

它们的关键字相应为{K1，K2，…，Kn}，

对记录序列进行排序就是要确定序号1，2，…，n的一种排列P1，P2，…，Pn，使其相应的关键字满足如下的非递减（或非递增）的关系：

Kp1<=Kp2<=…<=Kpn

使序列成为一个按关键字有序的序列

{Rp1，Rp2，…，Rpn}目的利用高效的查找方法，以提高查找效率。2/3/20233排序分类按待排序记录所在位置内部排序：待排序记录存放在内存。外部排序：排序过程中需对外存进行访问的排序。按排序依据原则插入排序：直接插入排序、折半插入排序、希尔排序。快速（交换）排序：冒泡排序、快速排序。选择排序：简单选择排序、堆排序。归并排序：2-路归并排序。基数排序2/3/20234稳定若待排序文件中有关键字相等的记录，排序后，其前后相对次序与排序前未发生变化，这种排序称为“稳定”排序；否则是“不稳定”排序。稳定排序与不稳定排序只是表示所用的排序方法，并不说明哪种方法好与差。排序基本操作比较两个关键字大小；将记录从一个位置移动到另一个位置；就全面性能而言，很难提出一种被认为最好的方法，每种方法均有优点和适用环境。2/3/20235本章讨论中，待排记录如下结构。#defineMAXSIZE20; //假设的顺序表最大长度

typeint

KeyType; //定义关键字类型为整数类型typedef

struct{

KeyTypekey;

//关键字项

InfoType

otherinfo;

//其它数据项

}RcdType; //记录类型typedef

struct{

RcdTyper[MAXSIZE+1];

//r[0]闲置或作为判别标志的“哨兵”单元

intlength;

//顺序表长度

}SqList； //顺序表类型2/3/2023610.2插入排序10.2.1直接插入排序基本思想整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序。2/3/2023749386597761327i=2(49)386597761327i=3(3849)6597761327i=4

(384965)97761327i=5

(38496597)761327i=6

(3849657697)1327i=1()i=7(133849657697)2727977665493827(13273849657697)排序结果：383849659797769776137665493813))))))))))))监视哨r[0]r[1]r[2]r[3]r[4]r[5]r[6]r[7]稳定的排序方法2/3/20238voidInsertSort(SqList&L){

//对顺序表L作直接插入排序

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

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

//将L.r[i]插入有序子表

L.r[0]=L.r[i]; //哨兵

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

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

//记录后移

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

//插入到正确位置

}//if

}//InsertSort直接插入排序的算法1

2

3

4

5

6

7

8时间复杂度T(n)=O(n²)2/3/20239算法评价时间复杂度若待排序记录按关键字从小到大排列(正序)

关键字比较次数：若待排序记录按关键字从大到小排列(逆序)

关键字比较次数：记录移动次数：2/3/202310若待排序记录是随机的，取平均值。关键字比较次数：记录移动次数：空间复杂度S(n)=O(1)2/3/20231110.2.2其它插入排序折半插入排序基本思想用折半查找方法确定插入位置的排序。i=1(30)1370853942620i=213(1330)70853942620i=76(6133039427085)20…i=820(6133039427085)20ihi=820(613203039427085)hmimhm插入位置2/3/202312voidBInsertSort(SqList&L){

//对顺序表L作折半插入排序

for(i=2;i<=L.length;++i){ L.r[0]=L.r[i];

//将L.r[i]暂存到L.r[0] low=1;high=i-1; while(low<=high){

//在r[low..high]中折半查找有序插入的位置

m=(low+high)/2;

//折半

if(LT(L.r[0].key，L.r[m].key))high=m-1;

//插入点在低半区

elselow=m+1;

//插入点在高半区

}//whilefor(j=i-1;j>=high+1;--j)L.r[j+1]=L.r[j];//记录后移

L.r[high+1]=L.r[0];

//插入

}}//BInsertSort时间复杂度：T(n)=O(n²)2/3/202313算法评价时间复杂度：T(n)=O(n²)空间复杂度：S(n)=O(1)折半插入排序只能减少排序过程中关键字比较的时间，并不能减少记录移动的时间。2/3/2023142-路插入排序基本思想

另设一个和L.r同类型的数组d，首先将L.r[1]赋给d[1]，并将d[1]看成是在排好序的序列中处于中间位置的记录，然后从L.r中第2个记录起依次插入到d[1]之前或之后的有序序列中。目的对折半插入排序的改进，减少记录的移动次数。2/3/202315初始关键字4938659776132749i=1(49)firstfinali=2(49)(38)firstfinali=3(4965)(38)firstfinali=4(496597)(38)firstfinal2/3/202316初始关键字4938659776132749i=4(496597)(38)firstfinali=5(49657697)(38)firstfinali=6(49657697)(1338)firstfinali=7(49657697)(132738)firstfinal2/3/202317初始关键字4938659776132749i=7(49657697)(132738)firstfinali=8firstfinal(4949657697)(132738)

2路插入排序的移动记录次数减少了，约为n2/8，但不能避免移动。2/3/20231810.2.3希尔(shell)排序基本思想是对插入排序的一个改进，也称缩小增量排序。先将整个待排序记录序列分割成若干个子序列，分别对这些子序列进行直接插入排序；待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。排序过程取一个正整数d1<n，把所有相隔d1的记录放一组，组内进行直接插入排序；然后取d2<d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止。2/3/202319初始关键字：49,38,65,97,76,13,27,49,55,4取d3=1三趟分组：三趟排序结果：一趟排序结果：二趟排序结果：取d1=5一趟分组：取d2=3二趟分组：493865977613274955413274955449386597761327495544938659776134493827495565977613449382749556597764132738494955657697不稳定的排序方法2/3/202320一趟希尔排序算法10.4voidShellInsert(SqList&L，int

dk){

//对顺序表L作一趟希尔插入排序。本算法是和一趟直接插入排序

//相比，作了如下修改：1.前后记录位置的增量是dk，不是1；

//2.r[0]只是暂存单元，不是哨兵。当j<=0时，插入位置已找到。

for(i=dk+1;i<=L.length;++i) if(LT(L.r[i].key,L.r[i-dk].key)){

//需将L.r[i]插入有序增量子表

L.r[0]=L.r[i];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}//ShellInsert2/3/202321希尔排序的算法10.5voidShellSort(SqList&L,int

dlta[],intt){

//按增量序列dlta[0..t-1]对顺序表L作希尔排序

for(k=0;k<t;++t) //一趟增量为dlta[k]的插入排序

ShellInsert(L,dlta[k]);}//ShellSort希尔排序的时间复杂度和所取增量序列相关，例如已有学者证明，当增量序列为2t-k-1(k=0,1,…，t-1)时，希尔排序的时间复杂度为O(n3/2)。2/3/202322希尔排序特点子序列的构成不是简单的“逐段分割”，而是将相隔某个增量的记录组成一个子序列。希尔排序可提高排序速度，因为分组后n值减小，n²更小，而T(n)=O(n²),所以T(n)从总体上看是减小了；关键字较小的记录跳跃式前移，在进行最后一趟增量为1的插入排序时，序列已基本有序。增量序列取法无除1以外的公因子；最后一个增量值必须为1；如……,9,5,3,2,1或……,31,15,7,3,1或……,40,13,4,1等。2/3/20232310.3交换排序起泡排序排序过程将第一个记录的关键字与第二个记录的关键字进行比较，若为逆序r[1].key>r[2].key，则交换；然后比较第二个记录与第三个记录；依次类推，直至第n-1个记录和第n个记录比较为止——第一趟冒泡排序，结果关键字最大的记录被安置在最后一个记录上。对前n-1个记录进行第二趟冒泡排序，结果使关键字次大的记录被安置在第n-1个记录位置重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作”为止。2/3/202324381327

4949第四趟后49384913273065第三趟后4938496513273076第二趟后493849657613273097第一趟后494938659776132749初始关键字132738

49第五趟后497697139727979713767627136527656513134949273827383849497649132738第六趟后时间复杂度最好情况（正序）比较次数：n-1

移动次数：0最坏情况（逆序）

比较次数：空间复杂度：S(n)=O(1)移动次数：为什么是比较次数的3倍？2/3/202325快速排序对起泡法的一种改进。基本思想通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序。2/3/202326排序过程对r[s……t]中记录进行一趟快速排序，附设两个指针i和j，设枢轴记录rp=r[s]，x=rp.key，初始时令i=s,j=t；首先，从j所指位置向前搜索第一个关键字小于x的记录，并和rp交换；再从i所指位置起向后搜索，找到第一个关键字大于x的记录，和rp交换；重复上述两步，直至i==j为止；再分别对两个子序列进行快速排序，直到每个子序列只含有一个记录为止。2/3/202327493865977613274927i初始关键字：jx49jii65j13i97jj494938659776132749初始关键字：完成一趟排序：2738134976976549一次划分后：(273813)49(76976549)分别进行快速排序：(13)

27

(38)

49(4965)

76(97)

(13)

27

(38)

49

49(65)

76(97)快速排序结束：13

27

3849

4965

76

97不稳定的排序方法2/3/202328一趟快速排序的算法10.6intPartition(SqList&L,intlow,inthigh){

//交换顺序表L中子表r[low..high]中的记录，枢轴记录到位，并返回

//其所在位置，此时，在它之前（后）的记录均不大（小）于它。

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];

//将比枢轴记录小的记录移到低端

while(low<high&&L.r[low].key<=pivotkey)

++low;

L.r[high]=L.r[low];

//将比枢轴记录大的记录移到高端

}//while L.r[low]=L.r[0];

//枢轴记录到位

returnlow;

//返回枢轴位置}//Partition2/3/202329快速排序算法10.7和10.8voidQsort(SqList&L,intlow,inthigh){

//对顺序表L中的子序列L.r[low…high]作快速排序

if(low<high){ //长度大于1

pivotloc=Partition(L,low,high); //将L.r[low…high]划分

Qsort(L,low,pivotloc-1); //对低子表排序

Qsort(L,pivotloc+1,high); //对高子表排序

}}//QsortvoidQuickSort(SqList&L){

//对顺序表L作快速排序

Qsort(L,1,L.length);}//QuickSort时间复杂度T(n)=O(n²)2/3/202330算法分析时间复杂度最好情况（每次总是选到中间值作枢轴）T(n)=O(nlog2n)最坏情况（每次总是选到最小或最大元素作枢轴）T(n)=O(n²)为防止最差情况的出现，一般采取“三者取中”法来确定枢轴。即在第一个记录和最后一个记录，以及中间位置的记录中，选取值为中间的那个来作枢轴，这样就能防止最差情况的出现。空间复杂度：需栈空间以实现递归最坏情况：S(n)=O(n)一般情况：S(n)=O(log2n)对随机的关键字序列，快速排序是目前被认为是最好的排序方法。2/3/20233110.4选择排序基本思想每一趟在n-i+1（i=1,2,…,n-1）个记录中选取关键字最小的记录，并将它和第i个记录进行互换，从而使其成为有序序列中第i个记录。10.4.1简单选择排序排序过程首先，通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换；再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换；重复上述操作，共进行n-1趟排序后，排序结束。2/3/202332

13(38659776492749)初始：(4938659776132749)i=11349i=22738i=3i=4i=5i=61327(659776493849)3865132738(9776496549)499713273849(76976549)49761327384976(9765)49766597132738497697(97)497665767697排序结束13273849769765()497676976576稳定的排序方法2/3/202333简单选择排序算法10.9voidSelectSort(SqList&L){

//对顺序表L作简单选择排序

for(i=1;i<L.length;++i){

//选择第i小的记录，并交换到位

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

//在L.r[i..L.length]中选择关键字最小的记录

if(LT(L.r[k].key,L.r[j].key))j=k; if(i!=j)L.r[j]L.r[i];

//与第i个记录互换

}//for}//SelectSort时间复杂度T(n)=O(n²)2/3/202334算法评价时间复杂度记录移动次数最好情况：0最坏情况：3(n-1)比较次数：空间复杂度：S(n)=O(1)2/3/20233510.4.3堆排序堆的定义n个元素的序列(k1,k2,……kn)，当且仅当满足下列关系时，称之为堆。或若将此序列对应的一维数组看成是一个完全二叉树，则ki为二叉树的根结点，k2i和k2i+1分别为ki的“左子树根”和“右子树根”。2/3/202336（96，83，27，38，11，9）（13，38，27，50，76，65，49，97）962791138831327384965765097大顶堆小顶堆2/3/202337堆排序将无序序列建成一个堆，得到关键字最小（或最大）的记录；输出堆顶的最小（大）值后，使剩余的n-1个元素重又建成一个堆，则可得到n个元素的次小值；重复执行，得到一个有序序列的过程。堆排序需解决的两个问题：如何由一个无序序列建成一个堆？(初始建堆)如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？2/3/202338第二个问题解决方法——筛选（以小顶堆为例）输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”。2/3/20233913273849657650979727384965765013输出：132749389765765013输出：139749382765765013输出：13,273849502765769713输出：13,276549502738769713输出：13,27,382/3/2023404965502738769713输出：13,27,387665502738499713输出：13,27,38,495065762738499713输出：13,27,38,499765762738495013输出：13,27,38,49,506597762738495013输出：13,27,38,49,509765762738495013输出：13,27,38,49,50,652/3/2023417665972738495013输出：13,27,38,49,50,659765762738495013输出：13,27,38,49,50,65,769765762738495013输出：13,27,38,49,50,65,76,972/3/202342筛选算法10.10voidHeapAdjust(SqList&H,ints,intm){

//已知H.r[s..m]中记录的关键字除H.r[s].key之外均满足堆的定义，//本函数调整H.r[s]的关键字，使H.r[s..m]成为一个大顶堆（对其中

//记录的关键字而言）

rc=H.r[s];

//暂存根结点的记录

for(j=2*s;j<=m;j*=2){

//沿关键字较大的孩子结点向下筛选

if(j<m&<(H.r[j].key,H.r[j+1].key))++j;

//j为关键字较大的孩子记录的下标

if(!LT(rc.key,H.r[j].key))break;

//不需要调整，跳出循环

H.r[s]=H.r[j];s=j;//将大关键字记录往上调

}//for H.r[s]=rc;

//回移筛选下来的记录}//HeapAdjust若改为小顶堆，该如何修改语句？j<m&<(H.r[j+1].key,H.r[j].key)LT(rc.key,H.r[j].key)2/3/202343第一个问题解决方法从无序序列的第n/2个元素（即此无序序列对应的完全二叉树的最后一个非终端结点）起，至第一个元素止，进行反复筛选。496538271376975049653827137650974913382765765097例如：含8个元素的无序序列（49，38，65，97，76，13，27，50）2/3/20234449133827657650971327384965765097496538271376975049653827137650974913382765765097例如：含8个元素的无序序列（49，38，65，97，76，13，27，50）2/3/202345堆排序算法10.11voidHeapSort(SqList&H){

//对顺序表H进行堆排序

for(i=H.length/2;i>0;--i)

//将H.r[1..H.length]建成大顶堆

HeapAdjust(H,i,H.length); for(i=H.length;i>1;--i){

H.r[1]H.r[i]; //将堆顶记录和当前未经排

//序的子序列H.r[1..i]中最

//后一个记录互相交换

HeapAdjust(H,1,i-1); //将H.r[1..i-1]重新调整为

//大顶堆

}//for}//HeapSort2/3/202346算法评价时间复杂度：最坏情况下T(n)=O(nlogn)筛选算法：最多从第1层筛到最底层，为完全二叉树的深度

log2n+1;初始建堆：调用筛选算法n/2次；重建堆：调用筛选算法n-1次。空间复杂度：S(n)=O(1)记录较少时，不提倡使用。不稳定的排序方法2/3/20234710.5归并排序归并将两个或两个以上的有序表组合成一个新的有序表。2-路归并排序排序过程设初始序列含有n个记录，则可看成n个有序的子序列，每个子序列长度为1；两两合并，得到n/2个长度为2或1的有序子序列；再两两合并，……如此重复，直至得到一个长度为n的有序序列为止。2/3/202348初始关键字：[49][38][65][97][76][13][27]一趟归并后：[3849][6597][1376][27]二趟归并后：[38496597][132776]三趟归并后：[13273849657697]稳定的排序方法2/3/202349两个有序序列归并为一个有序序列的算法10.12voidMerge(RcdTypeSR[],RcdType&TR[],inti,intm,intn){

//将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n] for(j=m+1,k=i;i<=m&&j<=n;++k){

//将SR中记录按关键字从小到大地复制到TR中

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

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

} while(i<=m)TR[k++]=SR[i++];//将剩余的SR[i..m]复制到TR while(j<=n)TR[k++]=SR[j++];//将剩余的SR[j..n]复制到TR}//Merge2/3/202350算法评价时间复杂度：T(n)=O(nlog2n)每趟两两归并需调用merge算法n/2h次（h为有序段长度）；整个归并要进行log2n趟。空间复杂度：S(n)=O(n)2/3/20235110.6基数排序10.6.1多关键字的排序多关键字排序例对52张扑克牌按以下次序排序：两个关键字：花色（<<<）

面值（2<3<……<A）

并且“花色”地位高于“面值”2<3<……<A<2<3<……<A<

2<3<……<A<2<3<……<A2/3/202352多关键字排序方法最高位优先法（MSD)：

先对最高位关键字k1排序，将序列分成若干子序列，每个子序列有相同的k1值；然后让每个子序列对次关键字k2（如面值）排序，又分成若干更小的子序列；依次重复，直至就每个子序列对最低位关键字kd排序；最后将所有子序列依次连接在一起成为一个有序序列。最低位优先法(LSD)：

从最低位关键字kd起进行排序，然后再对高一位的关键字排序，……依次重复，直至对最高位关键字k1排序后，便成为一个有序序列。2/3/202353MSD与LSD不同特点按MSD排序，必须将序列逐层分割成若干子序列，然后对各子序列分别排序。按LSD排序，不必分成子序列，对每个关键字都是整个序列参加排序；并且可不通过关键字比较，而通过若干次分配与收集实现排序。2/3/20235410.6.2链式基数排序基数排序一种借助"多关键字排序"的思想来实现"单逻辑关键字排序"的内部排序算法。基数排序的步骤设置10个队列，f[i]和e[i]分别为第i个队列的头指针和尾指针；第一趟分配对最低位关键字（个位）进行，改变记录的指针值，将链表中记录分配至10个链队列中，每个队列记录的关键字的个位相同；第一趟收集是改变所有非空队列的队尾记录的指针域，令其指向下一个非空队列的队头记录，重新将10个队列链成一个链表；重复上述两步，进行第二趟、第三趟分配和收集，分别对十位、百位进行，最后得到一个有序序列。2/3/202355初始状态：278109063930589184505269008083109589269278063930083184505008e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]一趟分配930063083184505278008109589269一趟收集：2/3/202356505008109930063269278083184589二趟收集：083184589063505269930e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]二趟分配008109278930063083184505278008109589269一趟收集：2/3/202357008063083109184269278505589930三趟收集：109008184930e[0]e[1]e[2]e[3]e[4]e[5]e[6]e[7]e[8]e[9]f[0]f[1]f[2]f[3]f[4]f[5]f[6]f[7]f[8]f[9]三趟分配063083269278505589505008109930063269278083184589二趟收集：稳定的排序方法2/3/202358算法评价时间复杂度：分配：T(n)=O(n)收集：T(n)=O(rd)T(n)=O(d(n+rd))其中：n——记录数

d——关键字数

rd——关键字取值范围空间复杂度：S(n)=2rd个队列指针+n个指针域空间2/3/20235910.7各种内部排序方法的比较讨论时间性能按平均的时间性能来分，有三类排序方法：时间复杂度为O(nlogn)

的方法有：快速排序、堆排序和归并排序，其中快速排序目前被认为是最快的一种排序方法，后两者之比较，在n值较大的情况下，归并排序较堆排序更快；时间复杂度为O(n2)

的有：插入排序、起泡排序和选择排序，其中以插入排序为最常用，特别是对于已按关键字基本有序排列的记录序列尤为如此，选择排序过程中记录移动次数最少；时间复杂度为O(n)

的排序方法基数排序。2/3/202360当待排记录序列按关键字顺序有序时，插入排序和起泡排序能达到O(n)的时间复杂度；而对于快速排序而言，这是最不好的情况，此时的时间性能蜕化为O(n2)，因此应尽量避免。选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。以上对排序的时间复杂度的讨论主要考虑排序过程中所需进行的关键字间的比较次数，当待排序记录中其它各数据项比关键字占有更大的数据量时，还应考虑到排序过程中移动记录的操作时间，有时这种操作的时间在整个排序过程中占的比例更大，从这个观点考虑，简单排序的