第8章 内部排序

第8章 内部排序

8.1 排序的基本概念所谓排序，就是要重新排列一个数据元素(或记录)序 列，使之按数据元素(或记录)的某个数据项值有序排 列。“数据元素”或“记录”是进行排序的基本单位， 把所有这些待排元素或记录称为“序列”。 根据在排序过程中是否涉及数据的内、外存交换，可 以将排序分成两类：外排序和内排序。在排序过程中， 若整个序列都是放在内存中处理，排序时不涉及数据 的内、外存交换，则称之为内部排序(简称内排序); 反之，若排序过程中要进行数据的内、外存交换，则 称之为外部排序。本章讨论的是内部排序，设定待排 序序列均采用的顺序存储，即使用一维数组存放记录。

朱昌杰 肖建于 编著

清华大学出版社

8.1 排序的基本概念空间代价一般是指执行时所需的辅助空间。若排序算 法所需的辅助空间并不依赖于问题的规模n,即辅助 空间是O(1),则称之为就地排序。非就地排序一般要 求的辅助空间为O(n)。排序算法的时间代价一般由执行过程中数据元素的总 比较次数和总移动次数来决定，需要分别考虑3种情 况下的代价：最小时间代价(最佳情况)、最大时间代 价(最坏情况)和平均时间代价(平均情况)。

朱昌杰 肖建于 编著

清华大学出版社

8.1 排序的基本概念待排序的数据元素类型定义如下： typedef struct { int key; …… ; /*其它数据项*/ }Rectype ;对于任意的数据元素序列，若在排序前后关键码值相 同的数据元素之间的相对位置保持不变，这样的排序 方法称为稳定的排序方法。若存在一组数据序列，在 排序前后相同关键码值数据的相对位置发生了变化， 那么这样的排序方法称为不稳定。朱昌杰 肖建于 编著 清华大学出版社

8.1 排序的基本概念待排序的数据元素类型定义如下： typedef struct { int key; …… ; /*其它数据项*/ }Rectype ;对于任意的数据元素序列，若在排序前后关键码值相 同的数据元素之间的相对位置保持不变，这样的排序 方法称为稳定的排序方法。若存在一组数据序列，在 排序前后相同关键码值数据的相对位置发生了变化， 那么这样的排序方法称为不稳定。朱昌杰 肖建于 编著 清华大学出版社

8.2 插入排序插入排序(Insertion Sort)的基本思想是：每 次将一个待排序的数据元素(或记录),按关键码 大小插入到前面已经排好序的子序列中，并使子 序列保持有序，直到全部记录插入完成为止。

朱昌杰 肖建于 编著

清华大学出版社

8.2.1 直接插入排序1.基本思路 假设待排序列中有n个记录，存放在数组r[1..n]中，则直 接插入排序按照以下步骤进行： ①初始情况下，序列中的有序部分只包含有一

个元素r[1]; ②将无序部分的首元素r[i] (1<i<n+1)插入到有序部分 r[1]~r[i-1]中。首先将r[i]的值保存起来，以腾出该记录所 占数组元素位置；从后往前依次将r[i]与有序部分中的记 录的关键码进行比较，比r[i]大的记录需后移一位；直到 出现r[i].key≥r[j].key,则找到了正确的位置，将r[i]插入 在j+1位置上。 ③重复执行第②步，直到序列中有序部分包含n个元素为 止。朱昌杰 肖建于 编著 清华大学出版社

8.2.1 直接插入排序2.直接插入排序算法 根据上述算法思想，可写出直接插入排序算法。 void stInsertsort (Rectype r[],int n) {int i,j; for (i=2;i<=n;i++) /*共进行n-1趟插入*/ { r[0]=r[i]; /*r[0]为监视哨*/ j=i-1; while (r[j].key>r[0].key) { r[j+1]=r[j]; j- -;} r[j+1]=r[0]; /*将r[0]即原r[i]记录内容插到r[j]后一位置*/ } }朱昌杰 肖建于 编著 清华大学出版社

8.2.1 直接插入排序2.直接插入排序算法

朱昌杰 肖建于 编著

清华大学出版社

8.2.1 直接插入排序3.性能分析 (1)时间性能分析 对于具有n个记录的序列，要进行n-1趟排序。 每趟排序的操作分为比较关键码和移动记录， 而这两种操作的执行次数取决于待排序列的初 始排列。

朱昌杰 肖建于 编著

清华大学出版社

8.2.1 直接插入排序3.性能分析 (1)时间性能分析最好情况：初始按正序排列,每趟排序过程只需1 次比较，当前记录保存在监视哨中移动1次，回 填到合适位置移动1次，共2次移动记录。总共有 n-1趟，因此， 比较次数： 1 n 1n i 2n

移动次数： 2 2(n 1)i 2

朱昌杰 肖建于 编著

清华大学出版社

8.2.1 直接插入排序3.性能分析 (1)时间性能分析

最坏情况：初始按逆序排列，在每趟排序过程中，需 要最多的比较次数和最多的数据移动次数。对于第i趟， 需要将元素插入到有序部分的最前面位置，需要同前 面的i个记录(包括监视哨)进行i次关键码比较；当前记 录保存在监视哨中发生1次移动，回填时移动1次，前 面序列r[1]~r[i-1]依次后移共i-1次，总共移动了i+1次 数据移动。总共有n-1趟，因此， 1 i 2 (n 2)(n 1) 比较次数： 移动次数： (i 1) 1 (n 4)(n 1) 2n i 2n

朱昌杰 肖建于 编著

i 2

清华大学出版社

8.2.1 直接插入排序3.性能分析 (1)时间性能分析 平均情况：第i趟排序操作需要和前面有序部分中大约 一半的记录进行比较，即大约比较i/2次，需要移动记 录也大约i/2次。由此，直接插入排序的时间复杂度在 平均情况和最坏情况下都为O(n2)。

朱昌杰 肖建于 编著

清华大学出版社

8.2.1 直接插入排序3.性能分析 (2)空间性能分析 从空间性能上看，直接插入排序算法在排序过程中仅 用了一个辅助单

元r[0]。因此，它的空间复杂度 S(n)=O(1)。 (3)稳定性 直接插入排序是一个稳定的排序算法。在排序过程中， 每次插入的记录只与临近记录逐个比较，直到找到第 一个不大于该记录的值为止。

朱昌杰 肖建于 编著

清华大学出版社

8.2.2 折半插入排序1.基本思路

折半插入排序与直接插入排序算法类似，其基本 操作仍是向有序部分插入一个记录，不同之处在 于采用折半法确定插入位置，并在位置确定后将 该位置之后的元素依次后移。

朱昌杰 肖建于 编著

清华大学出版社

8.2.2 折半插入排序2.折半插入排序算法 void binInsertsort(Rectype r[],int n) { int i,j,low,mid,hight; for (i=2; i<=n; i++) { r[0]=r[i]; /* 保存待插入元素r[i] */ low=0; hight=i-1; while (low<=hight) /*确定插入位置 */ { mid=(low+hight)/2; if (r[0].key>r[mid].key) low=mid+1; else hight=mid-1; } for (j=i-1; j>=hight+1; j--) r[j+1]=r[j]; /*后移元素，空出插入位置 */ r[high+1]=r[0]; } /* 将元素插入合适位置 */ } 折半插入排序只适应于顺序存储的序列。朱昌杰 肖建于 编著 清华大学出版社

8.2.2 折半插入排序

3.性能分析 对于具有n个记录的序列，要进行n-1趟排序。 (1)时间性能分析 已知使用折半查找算法进行定位需要比较的次数至多是，在每 一趟排序中都要为待插入元素查找合适位置，共需要进行n-1趟， 因此整个排序过程需要比较次数为O(nlog2n)。而数据的移动次 数跟直接插入排序算法相同，为O(n2)。 (2)空间性能分析 折半查找排序与直接插入排序算法一样，在排序过程中仅用了 一个辅助单元r[0]。因此，它的空间复杂度S(n)=O(1)。 (3)稳定性 折半插入排序是一个稳定的排序算法。朱昌杰 肖建于 编著 清华大学出版社

8.2.3 希尔排序1.基本思路 假设序列中有n个记录，则希尔排序的基本步骤为： ①按选定的距离分组 假设相邻两个元素的距离为1,按选定距离分组就是：彼 此相距指定距离的元素划为一组。初始时选定一个适当的 距离d1(d1<n); ②在每组内进行插入排序； ③修改距离，选一小于d1的距离d2; ④重复①②③步的分组和排序操作，直到取di=1(i>=1) , 即所有记录成为一个组为止。朱昌杰 肖建于 编著 清华大学出版社

8.2.3 希尔排序1.基本思路 设有的关键码序列为{49,38,65,97,76,13,27, 65’},增量di取为{5,3,1},则排序过程如图所示。

朱昌杰 肖建于 编著

清华大学出版社

本文来源：https://www.bwwdw.com/article/xe9h.html