(
课件网) 第 8 章 排序 8.1 概述 8.2 插入排序 8.3 交换排序 8.4 选择排序 8.5 归并排序 8.6 基数排序 8.7 各种内部排序方法比较 1. 直接插入排序 2. 折半插入排序 3. 希尔排序 1. 冒泡排序 2. 快速排序 1. 简单选择排序 2. 树型选择排序 3. 堆排序 8.1 概述 排序：有n个记录的序列{R1，R2，…，Rn}，其相应关键字的序列是{K1，K2， …，Kn }，相应的下标序列为1，2，…， n。通过排序，要求找出当前下标序列1，2，…， n的一种排列p1，p2， …，pn，使得相应关键字满足如下的非递减（或非递增）关系，即：Kp1≤ Kp2≤…≤ Kpn ，这样就得到一个按关键字有序的记录序列：{Rp1， Rp2， …， Rpn}。 内部排序与外部排序：根据排序时数据所占用存储器的不同，可将排序分为两类。一类是整个排序过程完全在内存中进行，称为内部排序；另一类是由于待排序记录数据量太大，内存无法容纳全部数据，排序需要借助外部存储设备才能完成，成为外部排序。 稳定排序与不稳定排序： 上面所说的关键字Ki可以是记录Ri的主关键字，也可以是次关键字，甚至可以是记录中若干数据项的组合。若Ki是主关键字，则任何一个无序的记录序列经排序后得到的有序序列是唯一的；若Ki是次关键字或是记录中若干数据项的组合，得到的排序结果将是不唯一的，因为待排序记录的序列中存在两个或两个以上关键字相等的记录。 假设Ki=Kj(1≤i≤n，1≤j≤n，i≠j)，若在排序前的序列中Ri领先于Rj(即i
