严蔚敏数据结构排序.ppt

第九章 内部排序• 分类：分类：•内部排序：全部记录都可以同时调入内存进行的排序内部排序：全部记录都可以同时调入内存进行的排序 •外部排序：文件中的记录太大，无法全部将其同时调入内存进行的排外部排序：文件中的记录太大，无法全部将其同时调入内存进行的排序• 定义：设有记录序列：定义：设有记录序列：{ R1、、R2 ……….. Rn } 其相应的关键字其相应的关键字序列为：序列为： { K1、、K2 ……….. Kn }; 若存在一种确定的关系：若存在一种确定的关系： Kx <= Ky <= … <= Kz则将记录序列则将记录序列 { R1、、R2 ……….. Rn } 排成按排成按该关键字有序的序列：该关键字有序的序列： { Rx、、Ry ……….. Rz } 的的操作，称之为操作，称之为排序 关系是任意的，如通常经常使用的小于、大于等关系关系是任意的，如通常经常使用的小于、大于等关系• 稳定与不稳定：若记录序列中的任意两个记录稳定与不稳定：若记录序列中的任意两个记录 Rx、、Ry 的关键字的关键字 Kx = Ky ；；如果在排序之前和排序之后，它们的相对位置保持不变，如果在排序之前和排序之后，它们的相对位置保持不变，则这种排序方法是稳定的，否则是不稳定的。

则这种排序方法是稳定的，否则是不稳定的§9.1 插入排序«直接插入排序v排序过程：整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序v算法描述例49 38 65 97 76 13 27i=2 38 (38 49) 65 97 76 13 27i=3 65 (38 49 65) 97 76 13 27i=4 97 (38 49 65 97) 76 13 27i=5 76 (38 49 65 76 97) 13 27i=6 13 (13 38 49 65 76 97) 27i=1 ( )i=7 (13 38 49 65 76 97) 2727jjjjjj977665493827 (13 27 38 49 65 76 97)排序结果： 0 1 2 3 4 5 6 7 v算法评价l时间复杂度u若待排序记录按关键字从小到大排列(正序)Y关键字比较次数：Y记录移动次数： 0 1 2 3 4 5 6 7 13 27 38 49 65 76 97u若待排序记录按关键字从大到小排列(逆序)Y关键字比较次数：Y记录移动次数： 0 1 2 3 4 5 6 7 97 76 65 49 38 27 13u若待排序记录是随机的，取平均值Y关键字比较次数：Y记录移动次数：T(n)=O(n²)l空间杂度：S(n)=O(1)«折半插入排序v排序过程：用折半查找方法确定插入位置的排序叫~例i=1 (30) 13 70 85 39 42 6 20i=2 13 (13 30) 70 85 39 42 6 20i=7 6 (6 13 30 39 42 70 85 ) 20…...i=8 20 (6 13 30 39 42 70 85 ) 20sjmi=8 20 (6 13 30 39 42 70 85 ) 20sjmi=8 20 (6 13 30 39 42 70 85 ) 20sjmi=8 20 (6 13 30 39 42 70 85 ) 20sji=8 20 (6 13 20 30 39 42 70 85 )v算法描述v算法评价l时间复杂度：T(n)=O(n²)l空间复杂度：S(n)=O(1)«希尔排序(缩小增量法)v排序过程：先取一个正整数d1r[2].key，则交换；然后比较第二个记录与第三个记录；依次类推，直至第n-1个记录和第n个记录比较为止——第一趟冒泡排序，结果关键字最大的记录被安置在最后一个记录上l对前n-1个记录进行第二趟冒泡排序，结果使关键字次大的记录被安置在第n-1个记录位置l重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作”为止例49 38 65 97 76 13 27 30 初始关键字38 49 65 76 13 27 30 97 第一趟38 49 65 13 27 30 76 第二趟38 49 13 27 30 65 第三趟38 13 27 30 49 第四趟13 27 30 38 第五趟384976971397279730971376767627301365276530651313494930492738273830381 2 3 4 5 6 7 8v算法描述v算法评价l时间复杂度u最好情况（正序）Y比较次数：n-1Y移动次数：0u最坏情况（逆序）Y比较次数：Y移动次数：l空间复杂度：S(n)=O(1)T(n)=O(n²)«快速排序v基本思想：通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序v排序过程：对r[s……t]中记录进行一趟快速排序，附设两个指针i和j，设枢轴记录rp=r[s]，x=rp.keyl初始时令i=s,j=tl首先从j所指位置向前搜索第一个关键字小于x的记录，并和rp交换l再从i所指位置起向后搜索，找到第一个关键字大于x的记录，和rp交换l重复上述两步，直至i==j为止l再分别对两个子序列进行快速排序，直到每个子序列只含有一个记录为止例初始关键字： 49 38 65 97 76 13 27 50 ijxji 完成一趟排序： ( 27 38 13) 49 (76 97 65 50) 分别进行快速排序： ( 13) 27 (38) 49 (50 65) 76 (97) 快速排序结束： 13 27 38 49 50 65 76 974927ijijij4965ji1349ij4997ij例初始关键字： 49 38 65 97 76 13 27 50 ijx.key=49ji 完成一趟排序： ( 27 38 13) 49 (76 97 65 50) 27ijijij65ji13ij4997ijv算法描述v算法评价l时间复杂度u最好情况（每次总是选到中间值作枢轴）T(n)=O(nlog2n)u最坏情况（每次总是选到最小或最大元素作枢轴）T(n)=O(n²)l空间复杂度：需栈空间以实现递归u最坏情况：S(n)=O(n)u一般情况：S(n)=O(log2n)T(n)=O(n²)§9.3 选择排序«简单选择排序v排序过程l首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换l再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换l重复上述操作，共进行n-1趟排序后，排序结束例初始： [ 49 38 65 97 76 13 27 ]kjjjjjjkki=11349一趟： 13 [38 65 97 76 49 27 ]i=2kkjjjjj2738二趟： 13 27 [65 97 76 49 38 ]三趟： 13 27 38 [97 76 49 65 ]四趟： 13 27 38 49 [76 97 65 ]五趟： 13 27 38 49 65 [97 76 ]六趟： 13 27 38 49 65 76 [97 ]排序结束： 13 27 38 49 65 76 97v算法描述v算法评价l时间复杂度u记录移动次数Y最好情况：0Y最坏情况：3(n-1)u比较次数：l空间复杂度：S(n)=O(1)T(n)=O(n²)«堆排序v堆的定义：n个元素的序列(k1,k2,……kn)，当且仅当满足下列关系时，称之为堆或(i=1,2,…...n/2)kik2ikik2i+1kik2ikik2i+1例 （96，83，27，38，11，9） 例 （13，38，27，50，76，65，49，97）962791138831327384965765097可将堆序列看成完全二叉树，则堆顶元素（完全二叉树的根）必为序列中n个元素的最小值或最大值v堆排序：将无序序列建成一个堆，得到关键字最小（或最大）的记录；输出堆顶的最小（大）值后，使剩余的n-1个元素重又建成一个堆，则可得到n个元素的次小值；重复执行，得到一个有序序列，这个过程叫~v堆排序需解决的两个问题：l如何由一个无序序列建成一个堆？l如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？v第二个问题解决方法——筛选l方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，若根结点值小于子树的根结点值则与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”例13273849657650979727384965765013输出：132749389765765013输出：139749382765765013输出：13 273849502765769713输出：13 276549502738769713输出：13 27 384965502738769713输出：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 657665972738495013输出：13 27 38 49 50 659765762738495013输出：13 27 38 49 50 65 769765762738495013输出：13 27 38 49 50 65 76 97l算法描述v第一个问题解决方法l方法：按关键字的初始序列建立一棵完全二叉树，然后从无序序列的第n/2个元素（即此无序序列对应的完全二叉树的最后一个非终端结点）起，至第一个元素止，进行反复筛选例 含8个元素的无序序列（49，38，65，97，76，13，27，50）49653827137697504965382713765097491338276576509749133827657650971327384965765097 1 2 3 4 5 6 7 8 49 38 65 97 76 13 27 5050971365381327494913382765765097l算法描述v算法评价l时间复杂度：最坏情况下T(n)=O(nlogn)l空间复杂度：S(n)=O(1)§9.4 归并排序«归并——将两个或两个以上的有序表组合成一个新的有序表，叫~«2-路归并排序v排序过程l设初始序列含有n个记录，则可看成n个有序的子序列，每个子序列长度为1l两两合并，得到n/2个长度为2或1的有序子序列l再两两合并，……如此重复，直至得到一个长度为n的有序序列为止将下属两个将下属两个已排序的顺序表合并成一个有序表。

已排序的顺序表合并成一个有序表顺序比较两者的相应元素，小者移入另一表中，反顺序比较两者的相应元素，小者移入另一表中，反复如此，直至其中任一表都移入另一表为止复如此，直至其中任一表都移入另一表为止0 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk0 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk70 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk70 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk7130 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk713490 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk713490 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk71349650 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk71349650 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk7134965760 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk7134965760 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk713496576800 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk713496576800 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk71349657680至此至此 B 表的元素都已表的元素都已移入移入 C 表，只需将表，只需将 A 表的剩余部分移入表的剩余部分移入 C 表即可。

表即可0 1 2 3 44913659776780AB0 1 2 3 4 5 6 7 Cijk71349657680至此至此 B 表的元素都已表的元素都已移入移入 C 表，只需将表，只需将 A 表的剩余部分移入表的剩余部分移入 C 表即可97例初始关键字： [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]l算法描述v算法评价l时间复杂度：T(n)=O(nlog2n)l空间复杂度：S(n)=O(n)§9.5 基数排序«多关键字排序v定义：例 对52张扑克牌按以下次序排序：2<3<……<A<2<3<……<A<2<3<……<A<2<3<……<A两个关键字：花色（ <<< ） 面值（2<3<……