数据结构耿国华高教版第9章.pptxVIP

第9章 内部排序;9.1 排序的基本概念 排序：有n个记录的序列{R1，R2，…，Rn}，其相应关键字的序列是{K1，K2， …，Kn }，相应的下标 序列为1，2，…， n。通过排序，要求找出当前下标序列1，2，…， n的一种排列p1，p2， …，pn，使得相应关键字满足如下的非递减（或非递增）关系，即：Kp1≤ Kp2≤…≤ Kpn ，这样就得到一个按关键字有序的记录序列：{Rp1， Rp2， …， Rpn}。;在排序过程中，一般进行两种基本操作： 比较两个关键字的大小； 将记录从一个位置移动到另一个位置。 对于第二种操作，需要采用适当地存储方式，即向量结构、链表结构以及记录向量与地址向量结合的表示方法。 我们重点来讨论在向量存储结构上各种排序方法的实现。;9.2 插入类排序;A) { 48 };假设待排序记录存放在r[1..n]之中，为了提高效率，我们附设;该算法的要点是：①使用监视哨r[0]临时保存待插入的记???。 ②从后往前查找应插入的位置。③查找与移动用同一循环完成。 直接插入排序算法分析： 从空间角度来看，它只需要一个辅助空间r[0]。 从时间耗费角度来看，主要时间耗费在关键字比较和移动元素上。 直接插入排序方法是稳定的排序方法。;9.2.2 折半插入排序;算法分析： 采用折半插入排序法，可减少关键字的比较次 数。每插入一个元素，需要比较的次数最大为折半判定树的深度，如插入第i个元素时，设i=2j,则需进行log2i次比较，因此插入n-1个元素的平均关键字的比较次数为O(nlog2n)。 虽然折半插入排序法与直接插入排序法相比较，改善了算法中比较次数的数量级，但其并未改变移动元素的时间耗费，所以折半插入排序的总的时间复杂度仍然是O(n2)。;9.2.3 希尔排序;希尔排序的过程如下：;希尔排序实际上是对直接插入排序的一种改进。; 在希尔排序中，增量序列的选取到目前为止尚未得到一个最佳值，但最后一次排序时的增量值必须为1。 一般选取增量序列的规则是：取di+1为 di /3 ～; 【例9.2】假设数组R有12个待排序的记录，它们的关键字分别为： (65, 34, 25, 87, 12, 38, 56, 46, 14, 77, 92, 23) 用希尔排序方法进行排序，请给出排序过程。 【解】希尔排序的过程如图8.2所示。 在图中，同一连线上关键字表明它们所属的记录是放在同一个组中的。由于数组待排序的记 录数n=12，若按di+1= di /2 选取增量序列，那么所得到的增量序列为：;图9.2;Step1 将n个元素数列分为n个部分，元素比较间距为d。 step2 在第i步，两元素比较的间距取;void ShellInsert(RecordType r[], int length, int delta);void shell_sort(rectype r[]) { int i, n, jump, change, temp, m; /* change为交换标志，jump为增量步长 jump=NUM; n=NUM; /* NUM为顺序表的实际长度*/; 【算法分析】希尔排序比直接插入排序速度快。希尔排序算法的时间复杂度在 O(nlog2n)～O(n2)之间，大致为O(n1.5)。 希尔排序算法的空间复杂度为O(1)。 由于希尔排序是按增量分组进行排序的，所以希尔排序是一种不稳定的排序方法。;9.3.2 快速排序; 快速排序的基本思想是：在待排序的n个记录 中任意选择一个记录作为标准记录（通常选第 一个记录作为标准记录），以该记录的关键字 为基准，将当前的无序区划分为左右两个较小 的无序子区，使左边无序子区中各记录的关键 字均小于基准记录的关键字，使右边无序子区 中各记录的关键字均大于或等于基准记录的关 键字，而标准记录则位于两个无序区的中间位 置上（也就是该记录最终排序的位置上），分 别对左右两个无序区继续进行上述的划分过程，直到无序区中所有的记录都排好序为止。 在快速排序中，将待排序区间按照标准记录关键字分为左右两个无序区的过程称为一趟快速排序（或一次划分）。;【例】假设n=8，数组R中8个记录的关键字分别为：;图9.5; 显然，经过一次划分后，标准记录将整个无序区分成左右两个无序区，用同样的方法对左右两个无序区继续进行划分，直到各个子区间的长度为1时终止。 图9.5是在快速排序执行过程中，每一次划分后关键字的排列情况，图中加阴影的记录为本次快速排序的基准记录。;图9.5;一趟快速排序的具体做法是：;/* 快速排序算法——对R[hs]到R[ht]进行快速排序 */ void quick_sort(r, hs, ht) /* 对R[hs]到R[ht]进行快速排 */ rectype r[]; int hs, ht