资源描述
Data Structure Page 1 2021/2/26 第十章 内部排序 学习目标 理解排序的定义和各种排序方法的特点，并能加以灵活应用。 排序 方法有不同的分类方法，基于 “ 关键字间的比较 ” 进行排序的方法 可以按排序过程所依据的不同原则分为插入排序、交换排序、选择 排序、归并排序和计数排序等五类。 掌握各种排序方法的时间复杂度的分析方法。 能从 “ 关键字间的比 较次数 ” 分析排序算法的平均情况和最坏情况的时间性能。按平均 时间复杂度划分，内部排序可分为三类： O (n2) 的简单排序方法， O (nlogn) 的高效排序方法和 O (dn)的基数排序方法。 理解排序方法 稳定 或 不稳定 的含义，弄清楚在什么情况下要求 应用的排序方法必须是稳定的。 Data Structure Page 2 2021/2/26 重点和难点 重点 ：希尔排序、快速排序、堆排序和归并排序等高效方法 难点 ：希尔排序、快速排序、堆排序和归并排序等高效方法 知识点 排序、直接插入排序、折半插入排序、表插入排序、希尔排序、 起泡排序、快速排序、简单选择排序、堆排序、 2-路归并排序、 基数排序、排序方法的综合比较。 Data Structure Page 3 2021/2/26 10.1 概述 排序 假设含有 n个记录的序列为： R1， R2， ， Rn， 它们的关键字相应为 K1， K2， ， Kn， 对记录序列进行 排序 就是要确定序号 1， 2， ， n的一种排列 P1， P2， ， Pn， 使其相应的关键字满足如下的 非递减（或非递增） 的关系： Kp1=Kp2= =Kpn 使序列成为一个按关键字有序的序列 Rp1， Rp2， ， Rpn 目的 利用高效的查找方法，以提高查找效率。 Data Structure Page 4 2021/2/26 排序分类 按待排序记录所在位置 内部排序 ：待排序记录存放在内存。 外部排序 ：排序过程中需对外存进行访问的排序。 按排序依据原则 插入排序 ：直接插入排序、折半插入排序、希尔排序。 交换排序 ：冒泡排序、快速排序。 选择排序 ：简单选择排序、堆排序。 归并排序 ： 2-路归并排序。 基数排序 Data Structure Page 5 2021/2/26 稳定 若待排序文件中有 关键字相等的记录，排序后，其前后相对次序 与排序前未发生变化 ，这种排序称为 “ 稳定 ” 排序；否则是 “ 不 稳定 ” 排序。 稳定排序与不稳定排序 只是表示所用的排序方法， 并不说明哪种 方法好与差。 排序基本操作 比较 两个关键字大小； 将记录从一个位置 移动 到另一个位置； 就全面性能而言， 很难提出一种被认为最好的方法 ，每种 方法均有优点和适用环境。 Data Structure Page 6 2021/2/26 本章讨论中，待排记录如下结构。 #define MAXSIZE 20; / 假设的顺序表最大长度 type int KeyType; / 定义关键字类型为整数类型 typedef struct KeyType key; / 关键字项 InfoType otherinfo; / 其它数据项 RcdType; / 记录类型 typedef struct RcdType rMAXSIZE+1; / r0闲置或作为判别标志的 “ 哨兵 ” 单元 int length; / 顺序表长度 SqList； / 顺序表类型 Data Structure Page 7 2021/2/26 10.2 插入排序 10.2.1 直接插入排序 基本思想 整个排序过程为 n-1趟插入 ，即 先将 序列中第 1个记录看成是一个 有序子序列 ，然后 从第 2个记录开始 ， 逐个进行插入 ， 直至整个 序列有序 。 Data Structure Page 8 2021/2/26 49 38 65 97 76 13 27 i=2 ( 49 ) 38 65 97 76 13 27 i=3 ( 38 49 ) 65 97 76 13 27 i=4 ( 38 49 65 ) 97 76 13 27 i=5 ( 38 49 65 97 ) 76 13 27 i=6 ( 38 49 65 76 97 )13 27 i=1 ( ) i=7 ( 13 38 49 65 76 97 ) 27 27 97 76 65 49 38 27 ( 13 27 38 49 65 76 97 ) 排序结果： 38 38 49 65 97 97 76 97 76 13 76 65 49 38 13 ) ) ) ) ) ) ) ) ) ) ) 监视哨 r0 r1 r2 r3 r4 r5 r6 r7 稳定的排序 方法 Data Structure Page 9 2021/2/26 void InsertSort ( SqList i=L.length; +i ) if ( LT( L.ri.key , L.ri-1.key ) / 将 L.ri 插入有序子表 L.r0 = L.ri; / 哨兵 L.ri=L.ri-1; for ( j=i-2; LT( L.r0.key , L.rj.key ; -j ) L.rj+1 = L.rj; / 记录后移 L.rj+1 = L.r0; / 插入到正确位置 / if / InsertSort 直接插入排序的算法 1 2 3 4 5 6 7 8 时间复杂度 T(n)=O(n) Data Structure Page 10 2021/2/26 算法评价 时间复杂度 若待排序记录按关键字从小到大排列 (正序 ) 关键字比较次数： 11 2 n n i 记录移动次数： 2 1 ( 1 ) n i n 若待排序记录按关键字从大到小排列 (逆序 ) 关键字比较次数： 2 )1)(2( 2 nnin i 记录移动次数： 2 )1)(4()1( 2 nnin i Data Structure Page 11 2021/2/26 若待排序记录是 随机 的，取平均值。 关键字比较次数： 4 2n 记录移动次数： 4 2n 空间复杂度 S(n)=O(1) Data Structure Page 12 2021/2/26 10.2.2 其它插入排序 折半插入排序 基本思想 用折半查找方法确定插入位置的排序。 i=1 (30) 13 70 85 39 42 6 20 i=2 13 (13 30) 70 85 39 42 6 20 i=7 6 (6 13 30 39 42 70 85 ) 20 i=8 20 (6 13 30 39 42 70 85 ) 20 i h i=8 20 (6 13 20 30 39 42 70 85 ) h m i m h m 插入位置 Data Structure Page 13 2021/2/26 void BInsertSort (SqList i=L.length; +i ) L.r0 = L.ri; / 将 L.ri暂存到 L.r0 low = 1; high = i-1; while (low=high+1; -j ) L.rj+1 = L.rj; / 记录后移 L.rhigh+1 = L.r0; / 插入 / BInsertSort 时间复杂度： T(n)=O(n) Data Structure Page 14 2021/2/26 算法评价 时间复杂度： T(n)=O(n) 空间复杂度： S(n)=O(1) 折半插入排序只能 减少排序过程中关键字比 较的时间，并不能减少记录移动的时间 。 Data Structure Page 15 2021/2/26 2-路插入排序 基本思想 另设一个 和 L.r同类型的 数组 d，首先 将 L.r1赋给 d1，并将 d1看成是 在排好序的序列中处于 中间位置的记录 ，然后 从 L.r 中第 2个记录起依次插入到 d1之前或之后的有序序列中 。 目的 对折半插入排序的改进，减少记录的移动次数。 Data Structure Page 16 2021/2/26 初始关键字 49 38 65 97 76 13 27 49 i=1 (49) first final i=2 (49) (38) first final i=3 (49 65) (38) first final i=4 (49 65 97) (38) first final Data Structure Page 17 2021/2/26 初始关键字 49 38 65 97 76 13 27 49 i=4 (49 65 97) (38) first final i=5 (49 65 76 97) (38) first final i=6 (49 65 76 97) (13 38) first final i=7 (49 65 76 97) (13 27 38) first final Data Structure Page 18 2021/2/26 初始关键字 49 38 65 97 76 13 27 49 i=7 (49 65 76 97) (13 27 38) first final i=8 first final (49 49 65 76 97) (13 27 38) 2路插入排序的 移动记录次数减少了 ， 约为 n2/8， 但不能避免移动 。 Data Structure Page 19 2021/2/26 10.2.3 希尔 (shell)排序 基本思想 是 对插入排序的一个改进 ，也称缩小增量排序。 先将整个 待排序记录序列分割成若干个子序列 ，分别对这些 子序 列进行直接插入排序 ；待整个序列中的记录 “ 基本有序 ” 时，再 对 全体记录进行一次直接插入排序 。 排序过程 取一个 正整数 d1n， 把所有 相隔 d1的记录放一组 ， 组内 进行 直接 插入排序 ； 然后 取 d2d1， 重复上述 分组和排序 操作 ； 直至 di=1， 即所有记录放进一个组中排序为止。 Data Structure Page 20 2021/2/26 初始关键字： 49,38,65,97,76,13,27,49,55,4 取 d3=1 三趟分组： 三趟排序结果： 一趟排序结果： 二趟排序结果： 取 d1=5 一趟分组： 取 d2=3 二趟分组： 49 38 65 97 76 13 27 49 55 4 13 27 49 55 4 49 38 65 97 76 13 27 49 55 4 49 38 65 97 76 13 4 49 38 27 49 55 65 97 76 13 4 49 38 27 49 55 65 97 76 4 13 27 38 49 49 55 65 76 97 不稳定的 排序方法 Data Structure Page 21 2021/2/26 一趟希尔排序算法 10.4 void ShellInsert ( SqList i0 j-=dk ) L.rj+dk = L.rj; / 记录后移，查找插入位置 L.rj+dk = L.r0; / 插入 / if / ShellInsert Data Structure Page 22 2021/2/26 希尔排序的算法 10.5 void ShellSort (SqList kr2.key， 则交换 ；然后比较 第二个记录与 第三个记录 ；依次类推， 直至第 n-1个记录和第 n个记录 比较 为止 第一趟冒泡排序 ， 结果关键字最大的记录被安置在 最后一个记录上 。 对前 n-1个记录进行第二趟冒泡排序 ，结果使关键字次大的记 录被安置在第 n-1个记录位置 重复上述过程， 直到 “ 在一趟排序过程中没有进行过交换记 录的操作 ” 为止。 Data Structure Page 25 2021/2/26 38 13 27 49 49 第 四 趟 后 38 49 13 27 30 65 第 三 趟 后 49 38 49 65 13 27 30 76 第 二 趟 后 49 38 49 65 76 13 27 30 97 第 一 趟 后 49 49 38 65 97 76 13 27 49 初 始 关 键 字 13 27 38 49 第 五 趟 后 49 76 97 13 97 27 97 97 13 76 76 27 13 65 27 65 65 13 13 49 49 27 38 27 38 38 49 49 76 49 13 27 38 第 六 趟 后 时间复杂度 最好情况（正序） 比较次数： n-1 移动次数： 0 最坏情况（逆序） 比较次数： 空间复杂度 ： S(n)=O(1) )(21)( 2 1 1 nnin n i )(23)(3 2 1 nninn i 移动次数： Data Structure Page 26 2021/2/26 快速排序 对起泡法的一种改进。 基本思想 通过 一趟排序 ，将 待排序记录分割成独立的两部分 ，其中 一部 分记录的关键字均比另一部分记录的关键字小 ，则可 分别对这 两部分记录进行排序 ，以达到整个序列有序。 Data Structure Page 27 2021/2/26 排序过程 对 rs t中记录进行一趟快速排序，附设两个指针 i和 j， 设枢轴记录 rp=rs， x=rp.key，初始时 令 i=s,j=t； 首先， 从 j所指位置向前搜索第一个关键字小于 x的记录，并 和 rp交换 ； 再 从 i所指位置起向后搜索，找到第一个关键字大于 x的记录， 和 rp交换 ； 重复上述两步， 直至 i=j为止 ； 再 分别对两个子序列进行快速排序 ， 直到每个子序列只含有 一个记录为止 。 Data Structure Page 28 2021/2/26 49 38 65 97 76 13 27 49 27 i 初始关键字： j x 49 j i i 65 j 13 i 97 j j 49 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 ( 97 ) ( 13 ) 27 ( 38 ) 49 49 (65) 76 ( 97 ) 快速排序结束： 13 27 38 49 49 65 76 97 不稳定的排 序方法 Data Structure Page 29 2021/2/26 一趟快速排序的算法 10.6 int Partition ( SqList /用子表的第一个记录作枢轴记录 pivotkey = L.rlow.key; / 枢轴记录关键字 while (low high) / 从表的两端交替地向中间扫描 while (low = pivotkey) -high; L.rlow+ = L.rhigh; / 将比枢轴记录小的记录移到低端 while (low high L.rhigh = L.rlow; / 将比枢轴记录大的记录移到高端 / while L.rlow = L.r0; / 枢轴记录到位 return low; / 返回枢轴位置 / Partition Data Structure Page 30 2021/2/26 快速排序算法 10.7和 10.8 void Qsort(SqList /将 L.rlow high划分 Qsort(L,low,pivotloc-1); /对低子表排序 Qsort(L, pivotloc+1,high); /对高子表排序 / Qsort void QuickSort(SqList / QuickSort 时间复杂度 T(n)=O(n) Data Structure Page 31 2021/2/26 算法分析 时间复杂度 最好情况（每次总是选到中间值作枢轴） T(n)=O(nlog2n) 最坏情况（每次总是选到最小或最大元素作枢轴） T(n)=O(n) 为防止最差情况的出现， 一般采取 “ 三者取中 ” 法来确定枢轴。 即在第一个记录和最后一个记录，以及中间位置的记录中，选取 值为中间的那个来作枢轴，这样就能防止最差情况的出现。 空间复杂度 ：需栈空间以实现递归 最坏情况： S(n)=O(n) 一般情况： S(n)=O(log2n) 对随机的关键字序列，快速排序是 目前被认为是最好的排序方法 。 Data Structure Page 32 2021/2/26 10.4 选择排序 基本思想 每一趟在 n-i+1（ i=1,2, ,n-1）个记录中选取关键字最小的记 录， 并将它和第 i个记录进行互换，从而 使其成为有序序列中第 i 个记录。 10.4.1 简单选择排序 排序过程 首先，通过 n-1次关键字比较 ， 从 n个记录中找出关键字最小的记 录 ，将它 与第一个记录交换 ； 再通过 n-2次比较 ，从剩余的 n-1个记录中 找出关键字次小的记录 ， 将它 与第二个记录交换 ； 重复上述操作， 共进行 n-1趟排序后，排序结束 。 Data Structure Page 33 2021/2/26 13 ( 38 65 97 76 49 27 49 ) 初始： ( 49 38 65 97 76 13 27 49 ) i=1 13 49 i=2 27 38 i=3 i=4 i=5 i=6 13 27 ( 65 97 76 49 38 49 ) 38 65 13 27 38 ( 97 76 49 65 49 ) 49 97 13 27 38 49 ( 76 97 65 49 ) 49 76 13 27 38 49 76 ( 97 65 ) 49 76 65 97 13 27 38 49 76 97 ( 97 ) 49 76 65 76 97 排序结束 13 27 38 49 76 97 65 ( ) 49 76 76 9765 76 稳定的排序 方法 Data Structure Page 34 2021/2/26 简单选择排序算法 10.9 void SelectSort (SqList iL.length; +i) / 选择第 i 小的记录，并交换到位 j = i; for ( k=i+1; k=L.length; k+ ) / 在 L.ri.L.length中选择关键字最小的记录 if ( LT( L.rk.key , L.rj.key ) j =k ; if ( i!=j ) L.rj L.ri; / 与第 i 个记录互换 / for / SelectSort 时间复杂度 T(n)=O(n) Data Structure Page 35 2021/2/26 算法评价 时间复杂度 记录移动次数 最好情况： 0 最坏情况： 3(n-1) 比较次数： )(21)( 2 1 1 nnin n i 空间复杂度 ： S(n)=O(1) Data Structure Page 36 2021/2/26 10.4.3 堆排序 堆的定义 n个元素的序列 (k1,k2, kn)， 当且仅当满足下列关系时， 称之为堆。 2 21 ii ii kk kk 或 2 21 ii ii kk kk 1 , 2 , , 2ni 若将 此序列 对应的一维数组 看成是一个完全二叉树 ，则 ki为二 叉树的根结点， k2i和 k2i+1分别为 ki的 “ 左子树根 ” 和 “ 右子树 根 ” 。 Data Structure Page 37 2021/2/26 （ 96， 83， 27， 38， 11， 9） （ 13， 38， 27， 50， 76， 65， 49， 97） 96 27 9 11 38 83 13 27 38 49 65 76 50 97 大顶堆 小顶堆 Data Structure Page 38 2021/2/26 堆排序 将无序序列建成一个堆，得到关键字最小（或最大）的记录；输 出堆顶的最小（大）值后，使剩余的 n-1个元素重又建成一个堆， 则可得到 n个元素的次小值；重复执行，得到一个有序序列 的过 程。 堆排序需解决的两个问题 ： 如何由一个 无序序列建成一个堆 ？ (初始建堆 ) 如何在输出堆顶元素之后， 调整 剩余元素，使之 成为一个新的堆 ？ Data Structure Page 39 2021/2/26 第二个问题解决方法 筛选（以 小顶堆 为例） 输出堆顶元素 之后， 以堆中最后一个元素替代之 ； 然后 将根结点值与左、右子树的根结点值进行比较 ， 并与其中小 者进行交换 ； 重复上述操作， 直至叶子结点，将得到新的堆， 称这个从堆顶至 叶子的调整过程为“筛选”。 Data Structure Page 40 2021/2/26 13 27 38 49 65 76 50 97 97 27 38 49 65 76 50 13 输出： 13 27 49 38 97 65 76 50 13 输出： 13 97 49 38 27 65 76 50 13 输出： 13,27 38 49 50 27 65 76 97 13 输出： 13,27 65 49 50 27 38 76 97 13 输出： 13,27,38 Data Structure Page 41 2021/2/26 49 65 50 27 38 76 97 13 输出： 13,27,38 76 65 50 27 38 49 97 13 输出： 13,27,38,49 50 65 76 27 38 49 97 13 输出： 13,27,38,49 97 65 76 27 38 49 50 13 输出： 13,27,38,49,50 65 97 76 27 38 49 50 13 输出： 13,27,38,49,50 97 65 76 27 38 49 50 13 输出： 13,27,38,49,50,65 Data Structure Page 42 2021/2/26 76 65 97 27 38 49 50 13 输出： 13,27,38,49,50,65 97 65 76 27 38 49 50 13 输出： 13,27,38,49,50,65,76 97 65 76 27 38 49 50 13 输出： 13,27,38,49,50,65,76,97 Data Structure Page 43 2021/2/26 筛选算法 10.10 void HeapAdjust (SqList / 暂存根结点的记录 for(j=2*s;j=m;j*=2 ) / 沿关键字较大的孩子结点向下筛选 if ( jm / j 为关键字较大的孩子记录的下标 if (!LT(rc.key, H.rj.key ) break; / 不需要调整，跳出循环 H.rs = H.rj; s = j; / 将大关键字记录往上调 / for H.rs = rc; / 回移筛选下来的记录 / HeapAdjust 若改为小顶堆， 该如何修改语句？ j0; -i ) / 将 H.r1.H.length 建成大顶堆 HeapAdjust ( H, i, H.length ); for ( i=H.length; i1; -i ) H.r1 H.ri; / 将堆顶记录和当前未经排 / 序的子序列 H.r1.i中最 / 后一个记录互相交换 HeapAdjust(H, 1, i-1); / 将 H.r1.i-1重新调整为 / 大顶堆 /for / HeapSort Data Structure Page 47 2021/2/26 算法评价 时间复杂度 ：最坏情况下 T(n)=O(nlogn) 筛选算法：最多从第 1层筛到最底层，为完全二叉树的深度 log2n+1; 初始建堆：调用筛选算法 n/2 次； 重建堆：调用筛选算法 n-1 次。 空间复杂度 ： S(n)=O(1) 记录较少时，不提倡使用 。 不稳定 的排序方法 Data Structure Page 48 2021/2/26 10.5 归并排序 归并 将两个或两个以上的有序表组合成一个新的有序表 。 2-路归并排序 排序过程 设初始序列含有 n个记录，则可看成 n个有序的子序列，每个 子序列长度为 1； 两两合并 ，得到 n/2个长度为 2或 1的有序子序列； 再两两合并， 如此重复， 直至得到一个长度为 n的有序序 列为止 。 Data Structure Page 49 2021/2/26 初始关键字： 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 稳定的排序 方法 Data Structure Page 50 2021/2/26 两个有序序列归并为一个有序序列的算法 10.12 void Merge (RcdType SR, RcdType i=m +k) / 将 SR中记录按关键字从小到大地复制到 TR中 if ( LQ(SRi.key, SRj.key) TRk = SRi+; else TRk = SRj+; while (i=m) TRk+ = SRi+; / 将剩余的 SRi.m 复制到 TR while (j=n) TRk+ = SRj+; / 将剩余的 SRj.n 复制到 TR / Merge Data Structure Page 51 2021/2/26 算法评价 时间复杂度： T(n)=O(nlog2n) 每趟两两归并需调用 merge算法 n/2h 次（ h为有序段长度）； 整个归并要进行 log2n 趟。 空间复杂度： S(n)=O(n) Data Structure Page 52 2021/2/26 10.6 基数排序 10.6.1 多关键字的排序 多关键字排序 例 对 52张扑克牌按以下次序排序： 两个关键字：花色（ ） 面值（ 23 A） 并且“花色”地位高于“面值” 23 A23 A 23 A23 A Data Structure Page 53 2021/2/26 多关键字排序方法 最高位优先法 （ MSD)： 先对最高位关键字 k1排序 ， 将序列分成若干子序列 ，每 个子序列有相同的 k1值； 然后 让每个子序列 对次关键字 k2 （ 如面值）排序 ，又分成若干更小的子序列；依次重复， 直 至就每个子序列对最低位关键字 kd排序 ；最后将所有子序列 依次连接在一起成为一个有序序列。 最低位优先法 (LSD)： 从最低位关键字 kd起进行排序 ，然后 再对高一位的关键字 排序 ， 依次重复， 直至对最高位关键字 k1排序后 ，便成 为一个有序序列。 Data Structure Page 54 2021/2/26 MSD与 LSD不同特点 按 MSD排序 ，必须 将序列 逐层 分割成若干子序列 ，然后 对 各子序列分别排序。 按 LSD排序，不必分成子序列，对每个关键字都是整个序 列参加排序 ；并且可不通过关键字比较，而通过若干次分 配与收集实现排序。 Data Structure Page 55 2021/2/26 10.6.2 链式基数排序 基数排序 一种 借助 多关键字排序 的思想来实现 单逻辑关键字排序 的内 部排序算法。 基数排序的步骤 设置 10个队列， fi和 ei分别为 第 i个队列的头指针和尾指针； 第一趟分配对最低位关键字（个位）进行 ，改变记录的指针值， 将链表中记录分配至 10个链队列中， 每个队列记录的关键字的个 位相同； 第一趟收集是改变所有非空队列的队尾记录的指针域，令其指向 下一个非空队列的队头记录，重新将 10个队列链成一个链表； 重复上述两步，进行第二趟、第三趟分配和收集， 分别对十位、 百位进行， 最后得到一个有序序列。 Data Structure Page 56 2021/2/26 初始状态： 278 109 063 930 589 184 505 269 008 083 109 589 269 278 063 930 083 184 505 008 e0 e1 e2 e3 e4 e5 e6 e7 e8 e9 f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 一 趟 分 配 930 063 083 184 505 278 008 109 589 269 一趟收集： Data Structure Page 57 2021/2/26 505 008 109 930 063 269 278 083 184 589 二趟收集： 083 184 589 063 505 269 930 e0 e1 e2 e3 e4 e5 e6 e7 e8 e9 f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 二 趟 分 配 008 109 278 930 063 083 184 505 278 008 109 589 269 一趟收集： Data Structure Page 58 2021/2/26 008 063 083 109 184 269 278 505 589 930 三趟收集： 109 008 184 930 e0 e1 e2 e3 e4 e5 e6 e7 e8 e9 f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 三 趟 分 配 063 083 269 278 505 589 505 008 109 930 063 269 278 083 184 589 二趟收集： 稳定的排序 方法 Data Structure Page 59 2021/2/26 算法评价 时间复杂度： 分配： T(n)=O(n) 收集： T(n)=O(rd) T(n)=O(d(n+rd) 其中： n 记录数 d 关键字数 rd 关键字取值范围 空间复杂度： S(n)=2rd个队列指针 +n个指针域空间 Data Structure Page 60 2021/2/26 10.7 各种内部排序方法的比较讨论 时间性能 按平均的时间性能来分，有三类排序方法： 时间复杂度为 O (nlogn) 的方法有： 快速排序、堆排序和归并排序，其中 快速排序目前被认为是 最快的一种排序方法 ，后两者之比较， 在 n 值较大的情况下， 归并排序较堆排序更快 ； 时间复杂度为 O (n2) 的有： 插入排序、起泡排序和选择排序，其中以 插入排序为最常用 ， 特别是对于已按关键字基本有序排列的记录序列尤为如此 ， 选择排序过程中记录移动次数最少 ； 时间复杂度为 O (n) 的排序方法 基数排序。 Data Structure Page 61 2021/2/26 当 待排记录序列按关键字顺序有序时，插入排序和起泡排序能达 到 O (n)的时间复杂度 ；而对于 快速排序而言，这是最不好的情 况，此时的时间性能蜕化为 O (n2)，因此应尽量避免。 选择排序、堆排序和归并排序的时间性能不随记录序列中关键字 的分布而改变 。 以上 对排序的 时间复杂度的讨论主要考虑 排序过程中所需进行的 关键字间的比较次数 ， 当待排序记录中其它各数据项比关键字占 有更大的数据量时，还应考虑到排序过程中移动记录的操作时间 ， 有时这种操作的时间在整个排序过程中占的比例更大，从这个观 点考虑，简单排序的三种排序方法中起泡排序效率最低。 Data Structure Page 62 2021/2/26 空间性能 指的是排序过程中 所需的辅助空间大小 。 所有的简单排序方法（包括： 插入、起泡和选择排序 ）和 堆排序 的空 间复杂度均为 O (1)。 快速排序 为 O (logn)，为递归程序执行过程中栈所需的辅助空间。 归并排序和基数排序 所需辅助空间最多，其空间复杂度为 O (n)。 排序方法的稳定性能 除希尔排序、快速排序和堆排序是不稳定的排序方法 外，本章讨论的 其它排序方法都是稳定的。 稳定性 是由方法本身决定的。一般来说， 排序过程中所进行的比 较操作和交换数据仅发生在相邻的记录之间，没有大步距的数据调整 时，则排序方法是稳定的。 Data Structure Page 63 2021/2/26 Data Structure Page 64 2021/2/26 本章小结 一般来说，在选择排序方法时，可有下列几种选择： 若待排序的记录个数 n值较小（例如 n30），则可选用插入排序法， 但若记录所含数据项较多，所占存储量大时，应选用选择排序法。 若待排序的记录个数 n值较大时，应选用快速排序法。但若待排序 记录关键字有 “ 有序 ” 倾向时，就慎用快速排序，而宁可选用堆排 序或归并排序，而后两者的最大差别是所需辅助空间不等。 快速排序和归并排序在 n值较小时的性能不及直接插入排序，因此 在实际应用时，可将它们和插入排序 “ 混合 ” 使用。如在快速排序 划分子区间的长度小于某值时，转而调用直接插入排序；或者对待 排记录序列先逐段进行直接插入排序，然后再利用 “ 归并操作 ” 进 行两两归并直至整个序列有序为止。 Data Structure Page 65 2021/2/26 基数排序的时间复杂度为 O (d n)，因此特别适合于待排记录数 n 值很大，而关键字 “ 位数 d ”较小的情况。并且还可以调整 “ 基数 ” （如将基数定为 100或 1000等）以减少基数排序的趟数 d 的值。 一般情况下，对单关键字进行排序时，所用的排序方法是否稳定 无关紧要。但当按 最次位优先 进行多关键字排序时 (除第一趟 外 )必须选用稳定的排序方法。 Data Structure Page 66 2021/2/26 基础知识题 以关键字序列 (503,087,512,061,908,170,897,275,653,426)为 例，手工执行以下排序算法，写出每一趟排序结束时的关 键码状态： (1) 直接插入排序； (2) 希尔排序 (增量 d1=5 )； (3) 快速排序； (4) 堆排序； (5) 归并排序； (6) 基数排序。 若对下列关键字序列进行快速排序或归并排序 ,分别写出 三次调用过程 Partition 和过程 Merge 后的结果。 ( Tim, Kay, Eva, Roy, Dot, Jon, Kim, Ann, Tom, Jim, Guy, Amy) Data Structure Page 67 2021/2/26 试问在 1题所列各种排序方法中，哪些是稳定的 ?哪些是不 稳定的 ?并为每一种不稳定的排序方法举出一个不稳定的 实例。 不难看出，对长度为 n的记录序列进行快速排序时，所需 进行的比较次数依赖于这 n 个元素的初始排列。 n=7 时在最好情况下需进行多少次比较 ? 请说明理由。 对 n=7 给出一个最好情况的初始排列实例。 Data Structure Page 68 2021/2/26 判别以下序列是否为堆（小顶堆或大顶堆）。如果不是， 则把它调整为堆（要求记录交换次数最少）。 (100, 86, 48, 73, 35, 39, 42, 57, 66, 21); (12, 70, 33, 65, 24, 56, 48, 92, 86, 33); (103, 97, 56, 38, 66, 23, 42, 12, 30, 52, 06, 20); (05, 56, 20, 23, 40, 38, 29, 61, 35, 76, 28, 100)。
展开阅读全文