数据结构 教学课件 宗大华 陈吉人 09排序.pdfVIP

第9章 排序 第9章 排序 9.1 排 序 的 基 本 概 念 9.1 9.2 插 入 排 序 9.2 9.3 交 换 排 序 9.3 9.4 选 择 排 序 9.4 排序，能使杂乱的无序数据变为有序。 在将数据按某种规则排列有序后，就能大大 提高对其查找和处理的效率。 本章主要介绍以下几个方面的内容：  排序的基本概念；  基本的插入排序（直接插入排序、折半插 入排序、表插入排序）算法；  基本的交换排序（冒泡排序、快速排序） 算法；  基本的选择排序（直接选择排序、堆排序） 算法。 9.1 排序的基本概念 9.1 排序的基本概念 给定一组记录：r1、r2、…、rn，对应 的关键字分别为：k1、k2、…、kn。将这些 记录重新排列成顺序为：rs1、rs2、…、 rsn，使得对应的关键字满足： ≤ ≤ ≤ ks1 ks2 … ksn的升序条件。这种重排 一 组记录、使其关键字值具有非递减顺序的过 程，就称为“排序”。 让关键字排序后表现出一种非递增关系 也是可以的，也是排序 让关键字排序后表现出一种非递增关系 也是可以的，也是排序。 假定待排序记录中存在有相同关键字。 若经某种排序之后，那些有相同关键字值的 记录间的相对位置保持不变，那么称这种排 序方法是“稳定的”，否则就是“不稳定 的”。 所谓“内排序”，是指待排记录序列全 部存放在内存，整个排序过程也都在内存里 完成；所谓“外排序”，是指内存中容纳不 下所有待排记录序列，排序过程中需要不断 地与外存进行数据交换。本章只介绍有关内 排序的算法。 9.2 插 入 排 序 9.2 插 入 排 序 插入排序的基本思想是：一趟一个地将 待排记录按照关键字大小，插入到已经排好 序的部分记录的适当位置中，使其成为一个 新的有序序列，直到所有待排记录全部插入 完毕。 9.2.1 直接插入排序 直接插入排序的基本思想是：初始时认 可第1个记录已排好序，从第2个记录开始， ≤ ≤ 总是用第i(2 i n)个记录与前面排好序的 − i 1个记录的子序列进行顺序比较，插入到 它的相应位置，得到i个排好序的子序列。 这一过程直进行到最后一个记录时结束。 例9-1 已知待排序记录的关键字为： 77，44，99，66，33，55，88，22 利用直接插入排序完成对它们的排序， 给出最终的排序结果。 解：把所有待排记录存放在一个一维数 组A里，如图9-1的“初始状态”所示。 图9-1 直接插入排序的过程 一维数组元素的存储结构应该如图9-2 所示： 图9-2 数据元素的存储结构 算法9-1 直接插入排序算法。 已知有n个记录的待排序列存放在一维 数组Ar里，该数组元素的存储结构如图9-2 所示，要求对其进行直接插入排序。算法名 为Ins_Sort()，参数为Ar、n。 直接插入排序是一种稳定排序算法。 Ins_Sort(Ar, n) { − for (i=2; i=n; i++) /* 总共要进行n 1次扫描 */ { temp = Ar[i]; /* 每次扫描总是把被考察关键字存 入临时单元 */ j = i-1; /* j规定了这次比较范围的上界 */ while ( (temp.keyAr[j].key)