数据结构课件习题第十章排序

概述插入排序交换排序归并排序基数排序各种排序方法的综合比较第十章排序选择排序10.1排序的基本概念

所谓排序,就是要整理表中的记录,使之按关键字递增(或递减)有序排列。其确切定义如下：输入：n个记录,R0,R1,…,Rn-1,其相应的关键字分别为k0,k1,…,kn-1。输出：Ri0,Ri1,…,Rin-1,使得ki0≤ki1≤…≤kin-1

(或ki0≥ki1≥…≥kin-1)。数据表(datalist):它是待排序数据对象的有限集合。内排序与外排序:

内排序是指在排序期间数据对象全部存放在内存的排序；外排序是指在排序期间全部对象个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序。排序算法的稳定性:如果在对象序列中有两个对象r[i]和r[j]，它们的关键码k[i]==k[j]，且在排序之前，对象r[i]排在r[j]前面。如果在排序之后，对象r[i]仍在对象r[j]的前面，则称这个排序方法是稳定的，否则称这个排序方法是不稳定的。待排序数据表的类型定义//c9-1.h待排记录的数据类型。在教科书第264页structRedType//记录类型{KeyTypekey;//关键字项，具体类型在主程中定义InfoTypeotherinfo;//其他数据项，具体类型在主程中定义};

//c9-2.h顺序表类型的存储结构。在教科书第264页#defineMAX_SIZE20//一个用作示例的小顺序表的最大长度structSqList//顺序表类型{RedTyper[MAX_SIZE+1];//r[0]闲置或用作哨兵单元intlength;//顺序表长度};

插入排序的过程是一个逐步扩大记录的有序序列长度的过程。经过一趟排序有序序列区无序序列区有序序列区无序序列区10.2插入排序(InsertSorting)基本思想：每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子表中的适当位置,直到全部记录插入完成为止。该算法适合于n较小的情况，时间复杂度为O(n2).

n

<=3012.2.1直接插入排序(StraightInsertionSort)待排元素序列：[53]2736156942第一次排序：[2753]36156942第二次排序：[273653]156942第三次排序：[15273653]6942第四次排序：[1527365369]42第五次排序：[152736425369]

直接插入排序示例对于有n个数据元素的待排序列，插入操作要进行n-1次基本思想：当插入第i(i

1)个对象时，前面的L.r[0],

L.r[1],…,L.r[i-1]已经排好序。这时，用L.r[i]的关键码与L.r[i-1],L.r[i-2],…的关键码顺序进行比较，找到插入位置即将L.r[i]插入，原来位置上的对象向后顺移。直接插入排序的算法

voidInsertSort(SqList&L){//对顺序表L作直接插入排序。算法10.1inti,j;

for(i=2;i<=L.length;++i)//从第2个记录到最后一个记录ifLT(L.r[i].key,L.r[i-1].key)//当前记录<前一个记录{//将L.r[i]插入[1..i-1]的有序子表中L.r[0]=L.r[i];//将当前记录复制为哨兵(存入[0]中)

for(j=i-1;LT(L.r[0].key,L.r[j].key);--j)//有序子表从后到前，若哨兵小于记录L.r[j+1]=L.r[j];//记录后移1个单元L.r[j+1]=L.r[0];//将哨兵(当前记录)插入到正确位置}}时间复杂度为o(n2)最好情况下，总的关键码比较次数为n-1，对象移动次数为2(n-1)。最坏情况下，总的关键码比较次数为(n+2)(n-1)/2

和对象移动次数为(n+4)(n-1)/2.平均情况下,关键码比较次数和对象移动次数约为n2/4。因此，直接插入排序的时间复杂度为

o(n2)。对于有n个数据元素的待排序列，插入操作要进行n-1次关键码比较次数和对象移动次数与对象关键码的初始排列有关。算法分析直接插入排序是一种稳定的排序方法。仅需一个附加辅助空间o(1)折半插入排序(BinaryInsertsort)基本思想:设在顺序表中有一个对象序列L.r[0],L.r[1],…,L.r[n-1]。其中，L.r[0],L.r[1],…,L.r[i-1]是已经排好序的对象。在插入L.r[i]时，利用折半搜索法寻找L.r[i]的插入位置。折半插入排序折半插入排序在寻找插入位置时，不是逐个比较而是利用折半查找的原理寻找插入位置。待排序元素越多，改进效果越明显。例：有6个记录，前5个已排序的基础上，对第6个记录排序。[1527365369]42

low

mid

high

[1527365369]42

low

high

mid

[1527365369]42

high

low[152736425369](high<low，查找结束，插入位置为low或high+1)(42>36)(42<53)折半插入排序的条件：在有序序列中插入一个关键字。voidBInsertSort(SqList&L){//对顺序表L作折半插入排序。改算法10.2inti,j,m,low,high;

for(i=2;i<=L.length;++i)//从第2个记录到最后一个记录ifLT(L.r[i].key,L.r[i-1].key)//当前记录<前一个记录，加此句

{//将L.r[i]插入[1..i-1]的有序子表中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;//折半(中点位置m)ifLT(L.r[0].key,L.r[m].key)//关键字小于中点关键字high=m-1;//插入点在低半区elselow=m+1;

//关键字大于等于中点关键字插入点在高半区

}//low>high，退出while循环，[high+1]是插入位置

for(j=i-1;j>=high+1;--j)//有序子表从后到前L.r[j+1]=L.r[j];//记录后移L.r[high+1]=L.r[0];//插入到[high+1]}}算法分析对分查找比顺序查找快，所以对分插入排序就平均性能来说比直接插入排序要快。o(n2)它所需要的关键码比较次数与待排序对象序列的初始排列无关，仅依赖于对象个数。nlog2n

当n较大时，总关键码比较次数比直接插入排序的最坏情况要好得多，但比其最好情况要差。在对象的初始排列已经按关键码排好序或接近有序时，直接插入排序比对分插入排序执行的关键码比较次数要少。对分插入排序的对象移动次数与直接插入排序相同，依赖于对象的初始排列。对分插入排序是一个稳定的排序方法。仅需一个附加辅助空间o(1)shell排序又称缩小增量排序(DiminishingIncrementSort)。基本思想：将整个待排记录序列分割成若干个子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序，就可以完成整个的排序工作。特点：子序列的构成不是简单“逐段分割”，而是将相隔某个增量的记录组成一个子序列。增量序列一般取ht＝n/2k(k＝1，2，…，[log2n])，其中n为待排序序列的长度。12.2.3希尔排序(ShellSort)希尔排序的算法voidShellInsert(SqList&L,intdk){//对顺序表L作一趟希尔插入排序。本算法和一趟直接插入排序相比，作了以下修改：//1.前后记录位置的增量是dk，而不是1;//2.L.r[0]只是暂存单元，不是哨兵。当j<=0时，插入位置已找到。算法10.4inti,j;for(i=dk+1;i<=L.length;++i)//从与第1个记录相差增量dk的记录到表尾ifLT(L.r[i].key,L.r[i-dk].key)//关键字小于前面记录的(按增量){//以下将L.r[i]插入有序增量子表L.r[0]=L.r[i];//当前记录暂存在L.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];//插入}}voidShellSort(SqList&L,intdlta[],intt){//按增量序列dlta[0..t-1]对顺序表L作希尔排序。算法10.5intk;for(k=0;k<t;++k)//对所有增量序列{ShellInsert(L,dlta[k]);

//一趟增量为dlta[k]的希尔插入排序printf("dlta[%d]=%d，第%d趟排序结果(仅输出关键字)",k,dlta[k],k+1);Print1(L);//输出顺序表L的关键字}}算法分析对特定的待排序对象序列，可以准确地估算关键码的比较次数和对象移动次数。但想要弄清关键码比较次数和对象移动次数与增量选择之间的依赖关系，并给出完整的数学分析，还没有人能够做到。移动次数相对于简单的直接插入排序而言会减少。10.3交换排序(ExchangeSort)

交换排序的基本思想：两两比较待排序记录的关键字,发现两个记录的次序相反时即进行交换,直到没有反序的记录为止。

两种交换排序:(1)冒泡排序(2)快速排序10.3.1冒泡排序（起泡排序）(BubbleSort)基本思想：通过无序区中相邻记录关键字间的比较和位置的交换,使关键字最小的记录如气泡一般逐渐往上“漂浮”直至“水面”。小的浮起，大的沉底。从右端开始比较。第一趟：第n个与第n-1个比较，小则交换；第n-1个与第n-2个比较，小则交换，…关键字最小的记录交换到最前一个位置上第二趟：对后n-1个记录进行同样的操作，关键字次小的记录交换到第2个位置上；依次类推，则完成排序。第六趟排序后第五趟排序后第四趟排序后第三趟排序后第二趟排序后第一趟排序后初始关键字基本思想：小的浮起，大的沉底。4936416511783665364156364165413641561178363641491156492525251149495611111125252525冒泡排序voidbubble_sort(inta[],intn){//将a中n个整数重新排列成自小至大的有序序列(在教科书第16页)inti,j,t;Statuschange;//调整的标志

for(i=n-1,change=TRUE;i>=1&&change;--i)//由后到前调整，change=FALSE时终止循环{change=FALSE;//本次循环未调整的标志

for(j=0;j<i;++j)//从第1个到倒数第2个if(a[j]>a[j+1])//前面的大于后面的{t=a[j];//前后交换a[j]=a[j+1];a[j+1]=t;change=TRUE;//设置调整的标志}}}冒泡排序时间复杂度为O(n2)冒泡排序的C程序段：Voidbubsort(RedTypeL[],intn){inti,x,j=1,k=1;while(j<n)&&(k>0);{k=0;for(i=1;i<=n-j;i++)if(L[i+1].key<L[i].key){k++;x=L[i];L[i]=L[i+1];L[i+1]=x;}j++;}/*while*/}/*Bobsort*/时间复杂度为O(n2)算法分析在记录的初始排列已经按关键码从小到大排好序时，此算法只执行一趟起泡，做n-1次关键码比较，不移动对象。正序:时间复杂度为O(n).最坏的情形是算法执行了n-1趟起泡，第i趟(1

i

n)做了n-i次关键码比较，执行了n-i次对象交换。逆序：时间复杂度为O(n2)起泡排序需要一个附加记录以实现记录值的对换。起泡排序是一个稳定的排序方法。适合于数据较少的情况。

10.3.2快速排序(QuickSort)

快速排序是由冒泡排序改进而得的。基本思想是：在待排序的n个记录中任取一个记录(通常取第一个记录),把该记录放入适当位置后,数据序列被此记录划分成两部分。所有关键字比该记录关键字小的记录放置在前一部分,所有比它大的记录放置在后一部分,并把该记录排在这两部分的中间(称为该记录归位),这个过程称作一趟快速排序。

首先对无序的记录序列进行“一次划分”，之后分别对分割所得两个子序列“递归”进行快速排序。无序的记录序列无序记录子序列(1)无序子序列(2)枢轴一次划分分别进行快速排序stlowhigh设R[s]=52为枢轴

将R[high].key和枢轴的关键字进行比较，要求R[high].key≥

枢轴的关键字

将R[low].key和枢轴的关键字进行比较，要求R[low].key≤

枢轴的关键字high23low80high14low52例如R[0]52lowhighhighhighlow

可见，经过“一次划分”，将关键字序列52,49,80,36,14,58,61,97,23,75调整为:23,49,14,36,(52)58,61,97,80,75

在调整过程中，设立了两个指针：low和high，它们的初值分别为：s和t，

之后逐渐减小high，增加low，并保证

R[high].key≥52，和R[low].key≤52,否则进行记录的“交换”。以后对所有的两部分分别重复上述过程,直至每部分内只有一个记录为止。简而言之,每趟使表的第一个元素放入适当位置,将表一分为二,对子表按递归方式继续这种划分,直至划分的子表长为1。voidQuickSort(RecTypeR[],ints,intt)

//对R[s]至R[t]的元素进行快速排序{intlow=s,high=t; if(s<t)//区间内至少存在一个元素的情况{ R[0]=R[s]; //用区间的第1个记录作为基准 while(low!=high)//从两端交替向中间扫描,直至low=high {while(high>low&&R[high].key>R[0].key)high--; if(low<high)//表示找到这样的R[high],R[i]、R[high]交换 {R[low]=R[high];low++;}while(low<high&&R[low].key<R[0].key)low++; if(low<high)//表示找到这样的R[low],R[low]、R[j]交换 {R[j]=R[low];high--;} } R[low]=R[0];QuickSort(R,s,high-1);//对左区间递归排序QuickSort(R,low+1,t);//对右区间递归排序}}划分算法分析(函数QuickSort)(1)最好情况:是每趟将序列一分两半，正好在表中间，将表分成两个大小相等的子表。同折半查找［log2n］.(2)最坏情况:已经排好序,快速排序将蜕变为冒泡排序，其时间复杂度为O(n2)。(3)

改进办法：取每个待排序对象序列的第一个对象、最后一个对象和位置接近正中的3个对象，取其关键码居中者作为基准对象。(4)平均计算时间:o(nlog2n)(5)快速排序是一种不稳定的排序方法。(6)适于n较大情况.实验结果表明：就平均计算时间而言，快速排序是我们所讨论的所有内排序方法中最好的一个。10.4选择排序(SelectionSort)

选择排序的基本思想：每一趟从待排序的记录中选出关键字最小的记录,顺序放在已排好序的子表的最后,直到全部记录排序完毕。

两种选择排序方法：(1)简单(直接)选择排序(2)堆排序有序序列R[1..i-1]无序序列R[i..n]

第i趟简单选择排序从中选出关键字最小的记录有序序列R[1..i]无序序列R[i+1..n]10.4.1简单选择排序(SimpleSelectionSort)基本思想：第i趟排序开始时,当前有序区和无序区分别为R[0..i-1]和R[i..n-1](0≤i＜n-1),该趟排序则是从当前无序区中选出关键字最小的记录R[k],将它与无序区的第1个记录R[i]交换,使R[0..i]和R[i+1..n-1]分别变为新的有序区和新的无序区。

简单选择排序(SimpleSelectionSort)思想：首先从1~n个元素中选出关键字最小的记录交换到第一个位置上。然后再从第2个到第n个元素中选出次小的记录交换到第二个位置上，依次类推。时间复杂度为O(n2)，适用于待排序元素较少的情况。intSelectMinKey(SqListL,inti){//返回在L.r[i..L.length]中key最小的记录的序号intj,k=i;//初始设[i]的关键字为最小，存i于kKeyTypemin=L.r[i].key;//[i]的关键字存于minfor(j=i+1;j<=L.length;j++)//依次与其他记录比较if(L.r[j].key<min)//找到更小的关键字{k=j;min=L.r[j].key;//分别将更小的赋给k和min}returnk;//返回序号}voidSelectSort(SqList&L){//对顺序表L作简单选择排序。算法10.9inti,j;RedTypet;for(i=1;i<L.length;++i)//选择第i小的记录，并交换到位{j=SelectMinKey(L,i);//在L.r[i..L.length]中选择key最小的记录if(i!=j){t=L.r[i];//与第i个记录交换，使得第i小的存于[i]L.r[i]=L.r[j];L.r[j]=t;}}}总时间复杂度O(n2)对象的移动次数与对象序列的初始排列有关。当这组对象的初始状态是按其关键码从小到大有序的时候，对象的移动次数为0，达到最少。最坏情况是每一趟都要进行交换，总的对象移动次数为3(n-1)。直接选择排序是一种不稳定的排序方法。算法分析

简单选择排序的关键码比较次数与对象的初始排列无关。第i趟选择具有最小关键码对象所需的比较次数总是n-i-1次，此处假定整个待排序对象序列有n个对象。因此，总的关键码比较次数为n(n-1)/2.总时间复杂度O(n2)

堆：是具有特定条件的顺序存储的完全二叉树，其特定条件是：任何一个非叶子结点的关键字大于等于（或小于等于）子女的关键字的值。(1)

堆的示例

897624331510112536497856(a):堆顶元素取最大值(b):堆顶元素取最小值(2)实现堆排序需主要解决两个问题：

（a）如何由一个无序序列建成一个堆？（b）输出堆顶元素后，如何将剩余元素调整成一个新的堆？10.4.2堆排序(HeapSort)小根堆大根堆堆排序(HeapSort)堆排序分为两个步骤：第一步，根据初始输入数据，利用堆的调整算法形成初始堆，第二步，通过一系列的对象交换和重新调整堆进行排序。

问题1：如何由一个任意序列建初堆？

一个任意序列看成是对应的完全二叉树，由于叶子结点可以视为单元素的堆，因而可以反复利用“筛选”法，自底向上逐层把所有以非叶子结点为根的子树调整为堆，直到将整个完全二叉树调整为堆。可以证明，最后一个非叶子结点位于［n/2］个元素，n为二叉树结点数目。因此，“筛选”须从第［n/2］个元素开始，逐层向上倒退，直到根结点。

建立初始的最大堆212525*491608012345i212525*164908025431i21254925*1608初始关键码集合21254925*1608i=2时的局部调整n=6,i=int(n/2)=3开始212525*491608012345i492525*16210802543121254925*160849252125*1608i=0时的局部调整形成最大堆i=1时的局部调整问题2:

当堆顶元素改变时，如何重建堆?

首先将完全二叉树根结点中的记录移出，根为空结点，以堆中最后一个元素替代之，该记录称为待调整记录。从根的左、右儿子中选出一个关键字较大的记录，如果该记录的关键字大于待调整记录的关键字，则将该记录上移至空结点中。此时，原来那个关键字较大的子结点相当于空结点。重复上述移动过程，直到空结点左、右子的关键字均不大于待调整记录的关键字，此时将待调整记录放入空结点即可。上述调整方法相当于把待调整记录逐步向下“筛”的过程，所以一般称为“筛选”法。492525*211608012345082525*16214902543149252125*160808252125*1649交换0号与5号对象,5号对象就位初始最大堆把自堆顶至叶子的调整过程称为“筛选‘。从一个无序序列建堆的过程就是一个反复”筛选“的过程。2525*082116490123451625*082521490254312525*210816491625*210825

49交换0号与4号对象,4号对象就位从0号到4号重新调整为最大堆25*1608212549012345081625*25214902543125*16210825

4908162125*

25

49交换0号与3号对象,3号对象就位从0号到3号重新调整为最大堆211625*082549012345081625*25214902543121160825*

25

49081621

25*

25

49交换0号与2号对象,2号对象就位从0号到2号重新调整为最大堆160825*212549012345081625*25214902543116082125*

25

490816

21

25*

25

49交换0号与1号对象,1号对象就位从0号到1号重新调整为最大堆voidHeapSort(HeapType&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){rc=H.r[1];H.r[1]=H.r[i];H.r[i]=rc;

//把堆顶元素与最后一个记录相交换HeapAdjust(H,1,i-1);//把H.r[1..i-1]重新调整为一个堆}}//HeapSort堆排序算法A:B:(A)首先将一个无序序列建成堆。(B)然后将堆顶元素（序列中的最大项）与堆中最后一个元素交换（最大项应该在序列的最后）。不考虑已经换到最后的那个元素，只考虑前n－1个元素构成的子序列，显然，该子序列已不是堆，但左、右子树仍为堆，可以将该子序列调整为堆。反复做第(B)步，直到剩下的子序列为空为止。适合较大规模的线性表，时间复杂度O(nlog2n)

堆排序在最坏情况下，其时间复杂度也为O(nlog2n)堆排序中只需要存放一个记录的辅助空间(称作原地排序)。堆排序是一种不稳定的排序方法适用于待排序记录个数n较大的文件是很有效的。算法分析10.5归并排序(MergeSort)初始序列[23][52][67][6][18][10]一趟归并后[2352][667][1018]二趟归并后[6235267][1018]三趟归并后[61018235267]归并排序示例功能：将两个或两个以上的有序表组成一个新的有序表。算法思想：把具有n个记录的表看成是n个有序的子表，每个子表的长度为1，然后两两归并，得到[n/2]个长度为2或为1的有序子表；再两两归并，如此重复，直到得到一个长度为n的有序表为止。算法分析:时间复杂度:(nlog2n)空间复杂度:和待排记录等量的空间.是一种稳定的排序方法。一般情况下很少用于内部排序.

与快速排序和堆排序相比，归并排序的最大特点是它为一种稳定的排序方法。一般情况下，由于要求附加与待排记录等数量的辅助空间，因此很少利用2路归并排序进行内部排序。算法总的时间复杂度为O(nlog2n)。

算法分析基数排序(RadixSort)基数排序是采用“分配”与“收集”的办法，用对多关键码进行排序的思想实现对单关键码进行排序的方法。（1）多关键码排序（2）链式基数排序例:每张扑克牌有两个“关键码”：花色和面值。其有序关系为：花色：

面值：2<3<4<5<6<7<8<9<10<J<Q<K<A如果我们把所有扑克牌排成以下次序：

2,…,

A,

2,…,

A,

2,…,

A,

2,…,

A这就是多关键码排序。排序后形成的有序序列叫词典有序序列。10.6.1多关键码排序最高位优先法MSD最低位优先法LSD例:学生成绩单按数学成绩的等级由高到低排序，数学成绩相同的学生再按英语成绩的高低等级排序。多关键码排序多关键码排序设有n个记录的序列{R1,R2,...,Rn}，Ri中含有d个关键字(Ki1，

Ki2，...，Kid)最高位优先法MSD通常是一个递归的过程：先根据最高位关键码K1排序,得到若干对象组，对象组中每个对象都有相同关键码K1。再分别对每组中对象根据关键码K2进行排序，按K2值的不同，再分成若干个更小的子组，每个子组中的对象具有相同的K1和K2值。依此重复，直到对关键码Kd完成排序为止。最后，把所有子组中的对象依次连接起来，得到一个有序的对象序列。最低位优先法LSD首先依据最低位关键码Kd对所有对象进行一趟排序，再依据次低位关键码Kd-1对上一趟排序的结果再排序，依次重复，直到依据关键码K1最后一趟排序完成，就可以得到一个有序的序列。使用这种排序方法对每一个关键码进行排序时，不需要再分组，而是整个对象组都参加排序。例：

2,…,

A,

2,…,

A,

2,…,

A,

2,…,

A链式基数排序是典型的最低位优先法LSD排序方法，利用“分配”和“收集”两种运算对单关键码进行排序。把单关键码Ki

看成是一个d元组：(Ki1，

Ki2，……,Kid)

(1

j

d)也可看成是一个关键码。10.6.2链式基数排序分量(1

j