数据结构内部排序.ppt

《数据结构内部排序.ppt》由会员分享，可在线阅读，更多相关《数据结构内部排序.ppt（81页珍藏版）》请在三一办公上搜索。

1、第10章 内部排序,学习目的与要求：,1.深刻理解排序的定义和各种排序方法的特点,并能加以灵活应用;,2.熟练掌握各种排序方法的执行过程；,3.熟练掌握各种排序方法的时间复杂度的分析方法，从“关键字间的比较次数和记录的移动次数”分析排序算法的平均情况和最坏情况的时间性能;,4.理解排序方法“稳定”或“不稳定”的含义。,基本内容,概述,插入排序,交换排序,选择排序,基数排序,归并排序,各种排序方法的比较,概述,1基本概念,排序：将数据元素(或记录)的一个任意序列,重新排列成一个按关键字有序的序列。,排序方法的稳定性：对关键字相同的数据元素，排序前后它们的领先关系保持不变，则称该排序方法是稳定的；

2、反之，称该排序方法是不稳定的。,内部排序：待排序记录存放在计算机的内存中进行的排序。,外部排序：待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序。,排序的时间开销：排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。算法运行时间代价的估算一般都按平均情况进行估算。对于那些受记录关键字序列初始排列及记录个数影响较大的，需要按最好情况和最坏情况进行估算。,2排序的分类,按排序过程依据的不同原则进行分类：,交换排序,选择排序,归并排序,计数排序,按工作量进行分类：,先进的排序方法，其时间复杂度为O(nlo

3、g2n),基数排序,基数排序，其时间复杂度为O(dn),3排序的基本操作和记录的存储方式,排序过程中需要的两种基本操作：（1）比较关键字的大小；（2）将记录从一个位置移至另一个位置。,待排序记录序列可有下列三种存储方式：（1）记录存放在一组连续的存储单元中；类似于线性表的顺序存储结构，记录次序由存储位置决定，实现排序需移动记录。（2）记录存放在静态链表中；记录次序由指针指示，实现排序不需移动记录，仅需修改指针。链排序（3）记录本身存放在一组连续的存储单元中，同时另设指示各个记录存储位置的地址向量，排序过程中不移动记录本身，而移动地址向量中相应记录的地址。排序结束后再根据地址调整记录的存储位置。

4、地址排序,4待排序记录的数据类型,#define MAXSIZE 20typedef struct int key;InfoType otherinfo;RedType;typedef struct RedType rMAXSIZE+1;/0单元作为哨兵 int length;SqList;,基本内容,概述,插入排序,交换排序,选择排序,基数排序,归并排序,各种排序方法的比较,插入排序,直接插入排序,插入排序的基本思想是：每步将一个待排序的记录，按其关键字大小，插入到前面已经排好序的一组记录的适当位置上，直到记录全部插入为止。,折半插入排序,2-路插入排序,表插入排序,希尔排序,插入排序,1直

5、接插入排序,基本思想：当插入第i(i 1)个记录时，前面的r1,r2，ri-1已经排好序。这时，用ri的关键字与ri-1，ri-2，的关键字顺序进行比较，找到插入位置即将ri插入，原来位置上之后的所有记录依次向后顺移。,例,49 38 65 97 76 13 27,（）,i=2 38(38 49)65 97 76 13 27,i=3 65(38 49 65)97 76 13 27,i=4 97(38 49 65 97)76 13 27,i=5 76(38 49 65 76 97)13 27,i=6 13(13 38 49 65 76 97)27,i=7(13 38 49 65 76 97)27

6、,97,27,76,65,49,38,排序结果：(13 27 38 49 65 76 97),直接插入排序的算法,void InsertSort(SqList/记录插入/InsertSort,时间复杂度：T(n)=O(n),结论：,空间复杂度：S(n)=O(1),直接插入排序是一个稳定的排序方法。,2折半插入排序,基本思想：利用直接插入排序的思想，只是在排序过程中，为减少查找次数，对已排好序的序列 r1,r1,ri-1，利用折半查找法寻找 ri 的插入位置。,例(30)13 70 85 39 42 6 20,i=2 13(13 30)70 85 39 42 6 20,.,i=7 6(6 13

7、30 39 42 70 85)20,i=8 20(6 13 20 30 39 42 70 85),算法描述如下：,void Bin_InsertSort(SqList/记录插入/Bin_InsertSort,算法分析,折半插入排序减少了关键字间的比较次数（由O(n)下降到O(nlog2n)。,折半插入排序的记录移动次数仍为O(n)。,折半插入排序的时间复杂度仍为O(n)，空间复杂度仍为O()。,折半插入排序是一个稳定的排序方法。,32-路插入排序,基本思想：利用直接插入排序的思想，只是在排序过程中，为减少记录的比较和移动次数，但需要n个记录的辅助空间。其做法是：另设一个和L.r同类型的数组D，

8、首先将L.r1赋给D.r1，并将D.r1看成是在排好序的序列中处于中间位置的记录，然后从L.r中第二个记录起依次到D.r1之前或之后的有序序列中。,例 30 13 70 85 39 42 6 20,排序过程中D的状态变化如下：,i=1(30),i=2(30)13,30 13 70 85 39 42 6 20,i=3(30)70 13,i=4(30)70 85 13,i=5(30)39 70 85 13,i=6(30)39 42 70 85 13,i=7(30)39 42 70 85 6 13,i=8(30)39 42 70 85 6 13 20,算法描述如下：,void Two_InsertS

9、ort(SqList L，SqList,for(k=first;k=high+1;k+)D.rk+1=D.rk;D.rhigh+1=L.ri;fianl+;/for/Two_InsertSort,算法分析,2-路插入排序减少了关键字间的比较次数(小于nlog2n)。,2-路插入排序减少了记录移动次数，约为n2/8。,2-路插入排序的时间复杂度仍为O(n)，但空间复杂度为O(n)。,2-路插入排序是一个稳定的排序方法。,4表插入排序,表插入排序采用了静态链表的存储结构，其排序过程如下：首先将静态链表中数组下标为1的分量（结点）和表头结点构成一个循环链表，然后依次将下标为2至n的分量（结点）按记录

10、关键字非递减有序插入到循环链表中。,表插入排序的基本操作仍是将一个记录插入到已排好序的有序表中。和直接插入排序相比，不同之处仅是以修改2n次指针值代替移动记录，排序过程中所需进行的关键字间的比较次数相同。因此，表插入排序的时间复杂度仍是O(n2)。,5希尔排序,希尔排序方法又称为“缩小增量”排序。,基本思想：先将整个待排序记录序列分割成若干子序列分别进行直接插入排序，待整个序列“基本有序”时，再对全体记录进行一次直接插入排序。,算法描述如下：,void ShellInsert(SqList,void ShellSort(SqList,希尔排序算法分析,子序列的构成不是简单的“逐段分割”，而是将

11、相隔某个增量的记录组成一个子序列；,希尔排序可提高排序速度，因为关键字较小的记录跳跃式前移，在进行最后一趟增量为1的插入排序时，序列已基本有序;,增量序列取法有多种：1)没有除1以外的公因子 2)最后一个增量值必须为1,时间复杂度是所取增量序列的函数，但至今没人能够给出完整的数学分析。,希尔排序是一个不稳定的排序方法。,基本内容,概述,插入排序,交换排序,选择排序,基数排序,归并排序,各种排序方法的比较,交换排序,起泡排序(Bubble Sort),交换排序的基本思想是：两两比较待排序记录的关键字，若两条记录的次序相反则进行交换，直到没有反序的记录为止。,快速排序(Quick Sort),交换

12、排序,1起泡排序(Bubble Sort),基本过程：1)将第一个记录的关键字与第二个记录的关键字进行比较，若为逆序r1.keyr2.key，则交换；然后比较第二个记录与第三个记录；依次类推，直至第n-1个记录和第n个记录比较为止第一趟冒泡排序，结果关键字最大的记录被安置在最后一个记录上;2)对前n-1个记录进行第二趟冒泡排序，结果使关键字次大的记录被安置在第n-1个记录位置;3)重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作”为止。,例：49 38 38 38 38 13 13 38 49 49 49 13 27 27 65 65 65 13 27 38 38 97 76 13

13、 27 49 49 76 13 27 49 49 13 27 49 65 27 49 76 49 97,初始关键字,第一趟排序后,第二趟排序后,第三趟排序后,第四趟排序后,第五趟排序后,第六趟排序后,算法分析,T(n)=O(n),空间复杂度：S(n)=O(1),起泡排序是一个稳定的排序方法,2快速排序(Quick Sort),对冒泡排序的一种改进,基本思想：通过一趟排序将待排序记录分割成独立的两部分，其中一部分的关键字均比另一部分的关键字小，则可分别对这两部分记录继续分别进行排序，以达到整个序列有序。,排序过程：,1)初始时令i=s,j=t;2)首先从j所指位置向前搜索第一个关键字小于pivo

14、t的记录，并和rp交换;3)再从i所指位置起向后搜索，找到第一个关键字大于pivot的记录，和rp交换;4)重复上述两步，直至i=j为止;（此时整个序列被分成有序的前后两块）5)再分别对两个子序列进行快速排序，直到每个子序列只含有一个记录为止。,对rst中记录进行一趟快速排序，附设两个指针i和j，设枢轴记录rp=rs，pivot=rp.key,快速排序举例,初始关键字：49，38，65，97，76，13，27，49,一趟完成后：27，38，13，49，76，97，65，49,一趟完成后：27，38，13，49，76，97，65，49,分别进行快速排序：13 27 38 49 49 65 76

15、97,快速排序结束：13 27 38 49 49 65 76 97,快速排序算法描述：,int Partition(SqList,void Qsort(SqList/QuickSort,快速排序算法分析,在n个元素的序列中，对一个记录定位所需时间为 O(n)。若设 T(n)是对 n 个元素的序列进行排序所需的时间，而且每次对一个记录正确定位后，正好把序列划分为长度相等的两个子序列，此时，总的计算时间为：T(n)cn+2 T(n/2)/c是一个常数 cn+2(cn/2+2T(n/4)=2cn+4T(n/4)2cn+4(cn/4+2T(n/8)=3cn+8T(n/8)cn log2n+nT(1)=

16、O(n log2n),快速排序的平均时间是O(nlogn)，在所有同数量级(O(nlogn)的排序方法中，就平均计算时间而言，快速排序是我们所讨论的所有内部排序方法中最好的一个。,快速排序需要一个栈空间来实现递归，若每趟排序都将记录序列均匀地分割成长度相接近的两个子序列，则栈的最大深度为O(logn)。,若初始序列按关键字基本有序（最坏情况），快速排序蜕化为起泡排序，其时间复杂度为O(n2)，最坏情况下栈的深度为n。,改进的方法，用“三者取中”的法则选取枢轴记录（pivotkey)。,快速排序是一种不稳定的排序方法。,对于 n 较大的平均情况而言，快速排序是“快速”的，但是当 n 很小时，这种

17、排序方法往往比其它简单排序方法还要慢。,基本内容,概述,插入排序,交换排序,选择排序,基数排序,归并排序,各种排序方法的比较,选择排序,选择排序(Selection Sort)的基本思想是：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子文件的最后，直到全部记录排序完毕。,简单选择排序(Select Sort),树形选择排序(Tree Selection Sort),堆排序(Heap Sort),选择排序,1简单选择排序(Select Sort),基本步骤：对长度为n的待排序序列进行简单选择排序需要经过n-1趟排序。第i 趟的排序过程为：在一组记录rirn(i=1,2,n-1)

18、中选择具有最小关键字的记录,并和第 i 个记录进行交换。,简单选择排序的算法void SelectSort(SqList,算法分析,简单选择排序的关键字比较次数与记录的初始排列无关。第 i 趟选择具有最小关键字的记录所需的比较次数是 n-i 次，若整个待排序序列有 n 条记录。因此，总的关键字比较次数为：,记录的移动次数与记录的初始排列有关。当初始状态是按其关键字从小到大有序的时候，记录的移动次数为 0，达到最少(最好情况)。最坏情况是每一趟都要进行交换，总的记录移动次数为3(n-1)。,简单选择排序是一种不稳定的排序方法。,简单选择排序的时间复杂度是O(n2)，空间复杂度是O(1)。,2树形

19、选择排序(Tree Selection Sort),又称锦标赛排序(Tournament Sort),是简单选择排序的改进(减少关键字间的比较次数)。,基本思想:与体育比赛时的淘汰赛类似。首先取得 n 个记录的关键字，进行两两比较，得到 n/2 个比较的优胜者(关键字小者)，作为第一步比较的结果保留下来。然后对这 n/2 个记录再进行关键字的两两比较，如此重复，直到选出一个关键字最小的记录为止。,如果 n 不是2的 k 次幂，则让叶子结点数补足到满足 2k-1个。叶结点上面一层的非叶结点是叶结点关键字两两比较的结果。最顶层是树的根。,每次两两比较的结果是把关键字小者作为优胜者上升到双亲结点，称

20、这种比赛树为胜者树。,位于最底层的叶结点叫做胜者树的外结点，非叶结点称为胜者树的内结点。每个结点除了存放记录的关键字 key 外，还存放了此记录是否要参选的标志 flag和此记录在满二叉树中的序号index。,形成初始胜者树（最小关键字上升到根）,关键字比较次数:7,关键字比较次数:2,关键字比较次数:2,说明：,锦标赛排序构成的树是完全二叉树，其深度为 log2n+1，其中 n 为待排序元素个数。,除第一次选择具有最小关键字的记录需要进行 n-1 次关键字比较外，重构胜者树选择具有次小、再次小关键字记录所需的关键字比较次数均为 log2n。总关键字比较次数为O(nlog2n)。,记录的移动次

21、数不超过关键字的比较次数，所以锦标赛排序总的时间复杂度为O(nlog2n)。,这种排序方法虽然减少了许多排序时间，但是使用了较多的附加存储。,锦标赛排序是一个稳定的排序方法。,3堆排序(Heap Sort),堆排序是树形选择排序的一种改进，主要是为了减少辅助存储空间和多余比较。,堆的定义：n个元素的序列k1,k2,kn当且仅当满足下列关系时，称之为堆。,例：（96，83，27，38，11，9）,例：（13，38，27，50，76，65，49，97）,可将堆序列看成完全二叉树,大顶堆,小顶堆,堆排序的基本思想是：把n个记录存于向量r之中，把它看成完全二叉树，此时关键字序列不一定满足堆的关系。堆排

22、序大体分两步处理：,第一步：初建堆。从堆的定义出发，当i=1,2,n/2时应满足kik2i和kik2i+1（或kik2i和kik2i+1）。所以先取i=n/2(它一定是第n个结点双亲的编号)将以i结点为根的子树调整为堆；然后令i=i-1，再将以i结点为根的子树调整为堆。此时可能会反复调整某些结点，直到i=1为止，堆初步建成。,第二步：堆排序。首先输出堆顶元素，让堆中最后一个元素上移到原堆顶位置，然后恢复堆，因为经过上移堆顶元素的操作后，往往破坏了堆关系，所以要恢复堆；重复执行输出堆顶元素、堆尾元素上移和恢复堆的步骤，直到全部元素输出完为止。,我们称这个从堆顶至叶子的调整过程为“筛选”。从一个无

23、序序列建堆的过程就是一个反复“筛选”的过程。,例如：根据输入序列49,38,65,97,76,13,27,49，建立一个小顶堆。,第一步：初建堆,第二步：堆排序。这是一个反复输出堆顶元素，将堆尾元素移至堆顶，再调整恢复堆的过程。恢复堆的过程与初建堆中i=1时所进行的操作完全相同。注意：每输出一次堆顶元素，堆顶与堆尾元素就交换一次，同时堆尾的逻辑位置退1，直到堆中剩下一个元素为止。,例如：对于给定的输入序列80,42,13,55,94,17,46，进行堆排序。,堆排序算法描述如下：,void HeapSort(HeapType,void HeapAdjust(HeapType,算法分析,时间复杂

24、度：最坏情况下T(n)=O(nlogn),空间复杂度：S(n)=O(1),对记录数较少的文件不值得提倡，但对n较大的文件很有效。,堆排序是一个不稳定的排序方法。,基本内容,概述,插入排序,交换排序,选择排序,基数排序,归并排序,各种排序方法的比较,归并排序(Merging Sort),归并排序(merge sort)是一类与插入排序、交换排序、选择排序不同的另一种排序方法。归并的含义是将两个或两个以上的有序表合并成一个新的有序表。归并排序有多路归并排序、2-路归并排序；可用于内部排序，也可以用于外部排序。我们仅对内部排序的2-路归并方法进行讨论。,2-路归并排序算法思路：(1)把n个记录看成n

25、个长度为1的有序子表；(2)进行两两归并使记录关键字有序，得到n/2个长度为2的有序子表；(3)重复第(2)步直到所有记录归并成一个长度为n的有序表为止。,例如：初始关键字：49 38 65 97 76 13 27,一趟归并之后：38 49 65 97 13 76 27,两趟归并之后：38 49 65 97 13 27 76,三趟归并之后：13 27 38 49 65 76 97,2-路归并排序中的核心操作是将一维数组中前后相邻的两个有序序列归并为一个有序序列，其算法描述如下：,void Merge(RcdType SR,RcdType/Merge,2-路归并排序的递归算法描述如下：,void

26、 MSort(RcdType SR,RcdType/将TR2s.m和TR2m+1.t归并到TR1s.t/MSort,void MergeSort(SqList/MergeSort,算法分析,在归并排序算法中，递归深度为O(log2n)，记录的关键字比较次数为O(nlog2n)。算法总的时间复杂度为O(nlog2n)。,归并排序所需的附助空间较多，需要一个与原待排序序列数组同样大小的辅助数组，所以算法的空间复杂度为O(n)。,归并排序是一个稳定的排序方法。,基本内容,概述,插入排序,交换排序,选择排序,基数排序,归并排序,各种排序方法的比较,基数排序(Radix Sort),基数排序是与前面所介

27、绍的排序方法完全不同的一种排序方法，该排序方法采用“分配”与“收集”的办法，用对多关键字进行排序的思想实现对单关键字进行排序的方法。,多关键字排序,以扑克牌排序为例：每张扑克牌有两个“关键字”：花色和面值。其有序关系为：花色：面值：2 3 4 5 6 7 8 9 10 J Q K A注：“花色”的地位高于“面值”,如果我们进行多关键字排序,可以把所有扑克牌排成以下次序：2,A,2,A,2,A,2,A,对于上例两关键字的排序，可以先按花色排序，之后再按面值排序；,也可以先按面值排序，再按花色排序（先按不同“面值”分成13堆，然后将这13堆牌自小至大叠在一起（大数放在小数的下面），然后将这付牌整个

28、颠倒过来再重新按不同“花色”分成4堆，最后将这4堆牌按自小至大的次序合在一起）。,一般情况下，假定有一个 n 个记录的序列 R1,R2,Rn，且每个记录Ri 中含有 d 个关键字(Ki0,Ki1,Kid-1).如果对于序列中任意两个记录 Ri 和 Rj(1 i j n)都满足：(Ki0,Ki1,Kid-1)(Kj0,Kj1,Kjd-1)则称序列R1,R2,Rn对关键字(K0,K1,Kd-1)有序。其中，K0称为最主位关键字，Kd-1称为最次位关键字。,实现多关键字排序通常有两种方法：最高位优先MSD(Most Significant Digit first)最低位优先LSD(Least Sig

29、nificant Digit first),最高位优先法先根据最主位关键字K0排序,得到若干子序列，每个子序列中每个记录都有相同关键字K0。再分别对每个子序列中记录根据关键字K1进行排序，按K1值的不同，再分成若干个更小的子序列，每个子序列中的记录具有相同的K0和K1值。依此重复，直到对关键字Kd-1完成排序为止。最后，把所有子序列中的记录依次连接起来，就得到一个有序的记录序列。,最低位优先法 首先依据最次位关键字Kd-1对所有记录进行一趟排序，再依据关键字Kd-2对上一趟排序的结果再排序，依次重复，直到依据关键字K0最后一趟排序完成，就可以得到一个有序的序列。使用这种排序方法对每一个关键字进

30、行排序时，不需要再分组，而是整个序列都参加排序。,MSD 和LSD方法也可应用于对一个关键字进行的排序。此时可将单关键字 Ki 看作是一个子关键字组：(Ki0,Ki1,Kid-1),链式基数排序,基数排序是典型的LSD排序方法，利用“分配”和“收集”两种运算对单关键字进行排序。在这种方法中，把单关键字 Ki 看成是一个d元组：(Ki0,Ki1,Kid-1)其中的每一个分量Kij(0 j d-1)也可看成是一个关键字。假设分量Kij 有radix种取值，则称radix为基数。,例如，关键字984可以看成是一个3元组(9,8,4)，每一位有0,1,9等10种取值，基数radix=10。关键字dat

31、a可以看成是一个4元组(d,a,t,a)，每一位有a,b,z等26种取值，radix=26。,针对d元组中的每一个分量Kij，把记录序列中的所有记录,按 Kij 的取值，先“分配”到radix(rd)个队列中去。然后再按各队列的顺序，依次把记录从队列中“收集”起来，这样所有记录按取值 Kij 排序完成。,如果对于所有记录的关键字K0,K1,Kn-1，依次对各位的分量，让 j=d-1,d-2,0，分别用这种“分配”、“收集”的运算逐趟进行排序，在最后一趟“分配”、“收集”完成后，所有记录就按其关键字的值从小到大排好序了。,各队列采用链式存储结构，分配到同一队列的关键字用链接指针链接起来。每一队列

32、设置两 个队列指针：front radix指示队头，rear radix 指向队尾。,以静态链表作为待排序序列的存储结构。在记录重排时不必移动记录，只需修改各记录的链接指针即可。,例如：待排序序列放在单链表中，如下所示：,278,109,063,930,589,184,505,269,008,083,第一趟分配,第一趟收集,930,063,083,184,505,278,008,109,589,269,第二趟分配,第二趟收集,505,008,109,930,063,269,278,083,184,589,第三趟分配,第三趟收集后的有序序列,算法分析,若每个关键字有d 位，需要重复执行d 趟“分

33、配”与“收集”。每趟对n个记录进行“分配”的时间复杂度为O(n)，对rd(rd是指每个关键字的取值范围)个队列进行“收集”的时间复杂度为O(rd)。总时间复杂度为O(d(n+rd)。,基数排序需要增加n+2rd个附加链接指针。,基数排序是稳定的排序方法。,基本内容,概述,插入排序,交换排序,选择排序,基数排序,归并排序,各种排序方法的比较,各种排序方法的比较,说明：,直接插入排序、折半插入排序、冒泡排序、锦标赛排序、归并排序、基数排序是稳定的排序方法；而希尔排序、快速排序、简单选择排序、堆排序是不稳定的排序方法。,直接插入排序、冒泡排序、简单选择排序是简单的排序方法，其时间复杂度都为O(n2)

34、，空间复杂度为O(1)。,快速排序、锦标赛排序、堆排序和归并排序是先进型的排序方法，其时间复杂度均为O(nlog2n)，空间复杂度分别为O(log2n)、O(n)、O(1)、O(n)。,希尔排序又称为缩小增量的排序，也是插入类排序的方法，但在时间上有较大的改进。其时间复杂度约为O(n1.3),空间复杂度为O(1)。,就平均时间性能而言，快速排序最佳，但最坏情况下的时间性能不如堆排序和归并排序。,当在 n 个数据（n很大）中选出最小的 几个数据时，堆排序最快。,归并排序对待排序关键字的初始排列不敏感，故排序速度较稳定。但所需辅助空间较多（O(n)）。,各种不同的排序方法应根据不同的环境及条件分别选择。一般而言，对于排序元素少的，可以选用时间复杂度为O(n2)的算法；对于元素多的，可选用时间复杂度为O(nlog2n)的算法。,简单排序以“直接插入排序”最简单，当序列“基本有序”或n较小时，它是最佳排序方法，通常用它与先进的排序方法诸如快速排序等结合使用。,基数排序最适合n很大而关键字较小的序列。,