数据结构PPT(第10章排序)

第10章内部排序

理解和熟悉各种内部排序的基本思想和过程；掌握内部排序算法的时间复杂度的分析方法和结论；要求能根据各种内部排序方法的优缺点及不同场合选择合适的排序方法。学习要点10.1概述排序：设含有n个记录的文件{R1,R2,...,Rn}，其相应的关键字为{K1，K2，...，Kn}，将记录按关键字值非递减（或非递增）顺序排列的过程，称为排序。对所有的Ki=Kj（i≠j），若排序前Ri领先于Rj，排序后Ri仍领先于Rj，则称该排序方法是稳定的，反之称为不稳定的。内部排序：待排序文件的全部记录存放在内存进行的排序，称为内部排序。外部排序：排序过程中需要进行内外存数据交换的排序，称为外部排序。10.1概述在排序过程中，通常进行两种基本操作：（1）比较两个关键字大小；（2）将记录从一个位置移到另一个位置。约定：待排序的一组记录存放在地址连续的一组存储单元中，它类似于线性表的顺序存储结构。待排的记录的数据类型定义如下：typedefstruct{intkey;InfoTypeotherinfo;}RedType;typedefstruct{RedTyper[MAXSIZE+1];intlength;}SqList;10.2插入排序10.2.1直接插入排序基本思想：将一个记录插入到已排好序的有序表中，得到一个新的、记录数增1的有序表。例如：已知待排序的一组记录为49、38、65、97、40、13、27。假设在排序过程中，前4个记录已按关键字递增的次序重新排列，构成一个含4个记录的有序序列{38，49，65，97}，现要将关键字为40的记录插入该序列中，则按从后向前的顺序对该序列进行查找，由于38<40<49，则76应插入到65和97之间，从而得到新的有序序列{38，40，49，65，97}，称该过程为一趟直接插入排序。

直接插入排序方法方法：将序列中的第一个记录看成是一个有序的子序列，从第二个记录起逐个进行插入，直至整个序列变成按关键字非递减有序序列为止。StatusInsertSort(SqList&L){for(i=2;i<=L.length;++i)if(LT(L.r[i].key,L.r[i-1].key)){L.r[0]=L.r[i];//复制为哨兵

L.r[i]=L.r[i-1];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];}//插入到正确位置

}//InsertSortL.r[0][初始关键字]：（49）38659776132749*i=2：（38）（3849）659776132749*i=3：（65）（384965）9776132749*i=4：（97）（38496597）76132749*i=5：（76）（3849657697）132749*i=6：（13）（133849657697）2749*i=7：（27）（13273849657697）49*i=8：（49）（1327484949*657697）

直接插入排序示例

对于排序的效率分析，主要从比较次数和移动次数两方面着手。直接插入排序的效率与待排文件的关键字排列有关，最好情况为O(n)，最坏情况为O(n2)。直接插入排序的平均时间复杂度为O(n2)。直接插入排序是稳定的。

直接插入排序效率分析基本思想：设在顺序表中有一个对象序列V[0],V[1],…,V[n-1]。其中,V[0],V[1],…,V[i-1]是已经排好序的对象。在插入V[i]时,利用折半搜索法寻找V[i]的插入位置。10.2.2折半插入排序voidBInsertSort(SqList&L){for(i=2;i<=L.length;++i){L.r[0]=L.r[i];low=1;high=i-1;while(low<=high){mid=(low+high)/2; if(LT(L.r[0].key,L.r[mid].key))high=mid-1; elselow=mid+1;}for(intj=i-1;j>=high+1;--j)L.r[j+1]=L.r[j]; L.r[high+1]=L.r[0];}}

和直接插入排序相比，折半插入排序仅减少了比较次数，而记录的移动次不变。其时间复杂度仍为O(n2)。

折半插入排序算法

基本思想：希尔排序先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，待整个序列中的元素基本有序时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前一种方法有较大提高。

1.

若待排序文件"基本有序"，即文件中具有特性：

r[i].key＜Max{r[j]}（其中1≤j＜i）的记录数较少，则文件中大多数记录都不需要进行插入。

2.

基本有序时，直接插入排序效率可以提高，接近于O(n)。10.2.3希尔排序例如，n=8，数组R的八个元素分别为：17，3，30，25，14，17*，20，9。下面给出希尔排序算法的执行过程。初始状态：d=417

3

30

25

14

17*

20

9第一趟结果：d=214

3

20

9

17

17*

30

25第二趟结果：d=11431792017*3035第三趟结果：39141717*203035

希尔排序示例voidShellInsert(SqList&L,intdk){for(i=dk+1;i<=L.length;++i){if(LT(L.r[i].key,L.r[i-dk].key)){ 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+gap]=L.r[j]; L.r[j+gap]=L.r[0];}}}voidShellSort(SqList&L,intdlta[],intt){for(intk=0;k<t;++k){

ShellInsert(L,dlta[k]);}}

希尔排序算法

对希尔排序的分析提出了许多困难的数学问题，特别是如何选择增量序列才能产生最好的排序效果，至今没有得到解决。为什么希尔排序的时间性能优于直接插入排序呢？当文件初基本有序时直接插入排序所需的比较和移动次数均较少。另一面，当n值较小时，n和n2的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度O(n2)差别不大。在希尔排序时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于文件较近于有序状态，所以新的一趟排序过程也较快。因此，希尔排序在效率上较直接接入排序有较大的改进。它的时间复杂度为O(n1.3)。

希尔排序性能分析1.

子文件（子序列）的构成不是简单地“逐段分割”，而是将相隔某个“增量”的记录组成一个子文件。2.

增量序列应是递减，且最后一个必须为1。3.

希尔排序法是不稳定的（由于希尔排序对每个子序列单独比较，在比较时进行元素移动，有可能改变相同关键字元素的原始顺序，因此希尔排序是不稳定的）。

希尔排序特点10.3快速排序1.起泡排序基本思想：首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换之，然后比较第二个记录和第三个记录的关键字。依次类推，直至第n-1个记录和第n个记录的关键字进行过比较为止。上述过程称作第一趟起泡排序，其结果使得关键字最大的记录被安置到最后一个记录的位置上。然后进行第二趟起泡排序，对前n-1个记录进行同样操作，其结果使得关键字次大的记录被安置到第n-1个记录的位置上。第i趟起泡排序是从L.r[1]到L.r[n-i+1]依次比较相邻两个记录的关键字，并在逆序时交换到第n-i+1的位置上。判别起泡排序结束条件是：在一趟排序过程中没有进行过交换记录的操作。初始关键字：4938659776132749第一趟排序后：3849657613274997第二趟排序后：38496513274976第三趟排序后：384913274965第四趟排序后：3813274949第五趟排序后：13273849第六趟排序后：132738

起泡排序示例voidBubbleSort(SqList&L){inti,j,tag;j=L.length-1;do{tag=1;for(i=1;i<=j;i++)if(L.r[i+1].key<L.r[i].key){L.r[0]=L.r[i+1];L.r[i+1]=L.r[i];L.r[i]=L.r[0];tag=0;}if(!tag)j--;}while(!tag&&j);return;}

起泡排序算法

在对象的初始排列已经按关键字从小到大排好序时，此算法只执行一趟起泡，做n-1次关键字比较，不移动对象。这是最好的情形。最坏的情形是算法执行了n-1趟起泡，第i趟(1≤

i＜n)做了n-i次关键字比较，执行了n-i次对象交换。总的时间复杂度为O(n2)。起泡排序是一个稳定的排序方法。

起泡排序算法分析

基本思想：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。一趟快速排序：首先选取一个记录（通常选取第一个记录）作为界点，然后将所有关键字较它小的记录都安置在它的位置之前，将所有关键字较它大的记录都安置在它的位置之后。由此以该“界点”记录最后所落的位置i为分界线，将整个序列分割成两个子序列。然后分别对这两个子序列重复施行上述方法，直到所有的对象都排在相应位置上为止。2.快速排序

附设两个指针low和high，其初值分别指向数组的单元1和单元n。选择第一个记录为界点，其关键字为pivotkey。将pivotkey复制到r[0]中，从high所指的位置起向前搜索找到第一个关键字小于pivotkey的记录复制到low所指位置中，然后从low所指位置起向后搜索，找到第一个关键字大于pivotkey的记录复制到high所指位置中，重复这两步直到low＝high为止。快速排序是对冒泡排序的一种改进方法，算法中元素的比较和交换是从两端向中间进行的，关键字较大的元素一次就能够交换到后面单元，关键字较小的记录一次就能够交换到前面单元，记录每次移动的距离较远，因而总的比较和移动次数较少。

具体做法012345

6782738659776132749*第一次交换lowhigh49012345

67

82738659776136549*第二次交换lowhigh49

具体实现过程012345

6784938659776132749*初始关键字pivotkeylowhigh49012345

6782738139776136549*第三次交换lowhigh49012345

6782738139776976549*第四次交换lowhigh49012345

6782738134976976549*第一趟完成lowhigh49

具体实现过程012345

67

82738659776136549*第二次交换lowhigh49

快速排序全过程

初始状态{4938659776132749}一趟快速排序后{273813}49{76976549}分别进行快速排序{13}27{38}结束结束{4965}76{97}49{65}结束结束

有序序列{1327384949657697}整个快速排序过程可递归进行intPartition(SqList&L,intlow,inthigh){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];}L.r[low]=L.r[0];returnlow;}

一趟快速排序算法实现voidQSort(SqList&L,intlow,inthigh){if(low<high){pivotloc=Partition(L,low,high);QSort(L,low,pivotloc-1);QSort(L,pivotloc+1,high);}}voidQuickSort(SqList&L){QSort(L,1,L.length);}

递归形式的快速排序算法

从时间上看，快速排序平均计算时间是O(nlog2n)。实验结果表明:就平均计算时间而言,快速排序是所有内排序方法中最好的一个。在最坏的情况,即待排序对象序列已经按其排序码从小到大排好序的情况下，其时间复杂度为O(n2)。从空间上看，快速排序是递归的，最大递归调用层次数与递归树的高度一致，理想情况为

log2(n+1)

。因此，要求存储开销为O(log2n)。快速排序是一种不稳定的排序方法。

算法分析10.4选择排序选择排序的基本思想是：每一趟(例如第i趟，i=1,…,n-1)在后面的n-i+1个待排序对象中选出关键字最小的对象，作为有序对象序列的第i个对象。待到第n-1趟作完，待排序对象只剩下1个，就不用再选了。1.简单选择排序

基本步骤为：i从1开始，直到n-1，进行n-1趟排序，第i趟的排序过程为：在一组对象r[i]～r[n]（i=1,2,…,n-1）中选择具有最小关键字的对象，并和第i个对象进行交换。voidSelectSort(SqList&L){for(i=1;i<L.length;++i){j=SelectMinKey(L,i);if(i!=j)L.r[i]←→L.r[j];}}//SelectSort

算法分析

直接选择排序的排序码比较次数与对象的初始排列无关。设整个待排序对象序列有n个对象,则第i趟选择具有最小排序码对象所需的比较次数总是n-i-1次。总的排序码比较次数为n(n-1)/2。对象的移动次数与对象序列的初始排列有关。当这组对象的初始状态是按其排序码从小到大有序的时候,对象的移动次数为0，达到最少。最坏情况是每一趟都要进行交换，总的对象移动次数为3(n-1)。直接选择排序是一种不稳定的排序方法。2.堆排序堆的定义：n个元素的序列{k1，k2，……，kn}，当且仅当满足以下关系时：

ki<=

k2iki>=

k2iki<=

k2i+1ki>=

k2i+1

其中i=1，2，…，

n/2

，则称此n个元素的关键字k1，k2，…，kn为一个堆。解释：如果让满足以上条件的元素序列{k1，k2，……，kn}顺次排成一棵完全二叉树，则此树的特点是：树中所有结点的值均大于（或小于）其左右孩子，此树的根结点（即堆顶）必最大（或最小）。或

大根堆和小根堆（a）小根堆（b）大根堆096517234578875331875378456509311723（09,17,65,23,45,78,87,53,31）（87,78,53,45,65,09,31,17,23）⑴以初始关键字序列，建立堆；⑵输出堆顶元素；⑶调整余下的元素，使其成为一个新堆；⑷重复⑵、⑶n次，得到一个有序序列。关键要解决⑴和⑶，即：如何由一个无序序列建成一个堆？如何在输出堆顶元素之后调整剩余元素成为一个新的堆？

堆排序基本思想

调整方法（以小根堆为例）1327384976654997972738497665491327973849766549132749384976659713⑴将堆顶元素和堆的最后一个元素位置交换；⑵然后以当前堆顶元素和其左、右子树的根结点进行比较（此时，左、右子树均为堆），并与值较小的结点进行交换；⑶重复⑵，继续调整被交换过的子树，直到叶结点或没进行交换为止。称这个调整过程为"筛选"。voidHeapAdjust(HeapType&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)&&(LT(H.r[j+1].key，H.r[j].key)))++j；

if(!(LT(H.r[j].key，rc.key)))break；

H.r[s].key=H.r[j].key；s=j；

}H.r[s]=rc;}

筛选算法

无序序列建立堆4965389776132749*方法：从完全二叉树的最后一个非终端结点└n/2┘开始（所有大于└n/2┘的结点都是叶子结点，以这些结点为根的子树均已是堆），反复调用筛选过程，直到第一个结点，则得到一个堆。例：（49，38，65，97，76，13，27，49*）。49653849*7613279749133849*7665279713493849*7665279713273849*76654997voidHeapSort(HeapType&H){for(i=H.length/2;i>0;--i)HeapAdjust(H，i，H.length);for(i=H.length；i>1；--i){temp=H.r[1];H.r[1]=H.r[i];H.r[i]=temp;HeapAdjust(H，1，i-1);}}

堆排序算法

在整个堆排序中，共需要进行└n/2+n-1┘次筛选运算，每次筛选运算进行双亲和孩子或兄弟结点的关键字的比较和移动次数都不会超过完全二叉树的深度，所以，每次筛选运算的时间复杂度为O(log2n)，故整个堆排序过程的时间复杂度为O(nlog2n)。堆排序不适合记录较少的文件，是一种不稳定的排序方法。该算法的附加存储主要是在第二个for循环中用来执行对象交换时所用的一个临时对象。因此，该算法的空间复杂性为O(1)。

算法分析归并：是将两个或两个以上的有序表合并成一个新的有序表。归并的基本操作是将两个位置相邻的有序记录子序列R[i..m]和R[m+1..n]归并成一个有序记录序列R[i..n]。2-路归并排序：基本思想：将两个有序子区间（有序表）合并成一个有序子区间，一次合并完成后，有序子区间的数目减少一半，而区间的长度增加一倍，当区间长度从1增加到n（元素个数）时，整个区间变为一个，则该区间中的有序序列即为我们所需的排序结果。10.4归并排序例如，已知关键字46，55，13，42，94，05，17，70，给出二路归并排序过程。初始状态：[46][55][13][42][94][05][17][70]

一趟归并：[4655][1342][0594][1770]

二趟归并：[13424655][05179470]

三趟归并：[0513174246557094]

归并过程

二路归并排序的时间复杂度等于归并趟数与每一趟时间复杂度的乘积。而归并趟数为

log2n

，每一趟归并的时间复杂度为O(n)。因此，二路归并排序的时间复杂度为O(nlog2n)。利用二路归并排序时，需要利用与待排序数组相同的辅助数组作临时单元，故该排序方法的空间复杂度为O(n)，比前面介绍的其它排序方法占用的空间大。二路归并排序是一种稳定的排序方法。

算法分析基数排序：是采用“分配”与“收集”的办法，利用对多关键字进行排序的思想实现对单关键字进行排序的方法。什么是多关键字排序？例：对52张扑克牌按以下次序排序：

2<

3<……<

A<

2<

3<……<

A<

2<

3<……<

A<

2<

3<……<

A

两个关键字：花色（