第9章 排序
本章主要内容： 1、插入类排序算法 2、交换类排序算法 3、选择类排序算法 4、归并类排序算法 5、基数类排序算法 本章重点难点 1、希尔排序 2、快速排序 3、堆排序
4、归并排序
9.1 基本概念
1．关键字 能标识数据元素的某个数据项。如果某个数据项可以唯一地确定一个数据元素，就将其称为主关键字；否则，称为次关键字。
2．排序 是把一组无序地数据元素按照关键字值递增（或递减）地重新排列。如果排序依据的是主关键字，排序的结果将是唯一的。
3. 排序算法的稳定性 如果在待排序的记录序列中有多个数据元素的关键字值相同，经过排序后，这些数据元素的相对次序保持不变，则称这种排序算法是稳定的，否则称之为不稳定的。
4. 内部排序与外部排序 根据在排序过程中待排序的所有数据元素是否全部被放置在内存中，可将排序方法分为内部排序和外部排序两大类。内部排序是指在排序的整个过程中，待排序的所有数据元素全部被放置在内存中；外部排序是指由于待排序的数据元素个数太多，不能同时放置在内存，而需要将
一部分数据元素放置在内存，另一部分数据元素放置在外设上，整个排序过程需要在内外存之间多次交换数据才能得到排序的结果。本章只讨论常用的内部排序方法。
5. 排序的基本方法 内部排序主要有5种方法：插入、交换、选择、归并和基数。
6. 排序算法的效率 评价排序算法的效率主要有两点：一是在数据量规模一定的条件下，算法执行所消耗的平均时间，对于排序操作，时间主要消耗在关键字之间的比较和数据元素的移动上，因此我们可以认为高效率的排序算法应该是尽可能少的比较次数和尽可能少的数据元素移动次数；二是执行算法所需要的辅助存储空间，辅助存储空间是指在数据量规模一定的条件下，除了存放待排序数据元素占用的存储空间之外，执行算法所需要的其他存储空间，理想的空间效率是算法执行期间所需要的辅助空间与待排序的数据量无关。
7. 待排序记录序列的存储结构 待排序记录序列可以用顺序存储结构和和链式存储结构表示。在本章的讨论中（除基数排序外），我们将待排序的记录序列用顺序存储结构表示，即用一维数组实现。其定义如下所示： #define MAX_NUM 80 //待排序记录序列中的最大数据元素个数 typedef struct elemtype { //待排序的数据元素类型 keytype key; //数据元素的关键字
anytype otherelem; //数据元素中的其他成份 } DataType[MAX_NUM+1]; 9.2 插入排序
插入排序的主要思路是不断地将待排序的数值插入到有序段中，使有序段逐渐扩大，直至所有数值都进入有序段中位置。
9.2.1 直接插入排序
1. 直接插入排序的基本思想
直接插入排序是一种比较简单的排序方法。它的基本思想是依次将记录序列中的每一个记录插入到有序段中，使有序段的长度不断地扩大。其具体的排序过程可以描述如下：首先将待排序记录序列中的第一个记录作为一个有序段，将记录序列中的第二个记录插入到上述有序段中形成由两个记录组成的有序段，再将记录序列中的第三个记录插入到这个有序段中，形成由三个记录组成的有序段，……依此类推，每一趟都是将一个记录插入到前面的有序段中，假设当前欲处理第i个记录，则应该将这个记录插入到由前i-1个记录组成的有序段中，从而形成一个由i个记录组成的按关键字值排列的有序序列，直到所有记录都插入到有序段中。一共需要经过n-1趟就可以将初始序列的n个记录重新排列成按关键字值大小排列的有序序列。 2. 直接插入排序算法
将第i个记录插入到由前面i-1个记录构成的有序段中主要有两个步骤： （1） 将待插入记录a[i] 保存在a[0]中，即a[0]=a[i]; （2）搜索插入位置：
j=i-1; //j最初指示i的前一个位置 while (a[0].key
{ a[j+1]=a[j]; //后移关键字值大于a[0].key的记录 j=j-1; //将j指向前一个记录，为下次比较做准备 }
a[j+1]=a[0]; //将a[0]放置在第j+1个位置上
完整的插入排序算法为：void insertsort (DataType a, int n)
{ for (i=2; i<=n; i++) //需要n-1趟 { a[0]=a[i]; //将a[i]赋予监视哨 j=i-1;
while (a[0].key
j=j-1; }
a[j+1]=a[0]; // 将原a[i]中的记录放入第j+1个位置 } }
直接插入排序算法简单、容易实现，只需要一个记录大小的辅助空间用于存放待插入的记录（在C语言中，我们利用了数组中的0单元）和两个int型变量。当待排序记录较少时，排序速度较快，但是，当待排序的记录数量较大时，大量的比较和移动操作将使直接插入排序算法的效率降低；然而，当待排序的数据元素基本有序时，直接插入排序过程中的移动次数大大减少，从而效率会有所提高。
插入排序是一种稳定的排序方法。 9.2.2 希尔排序
1. 希尔排序的基本思想
希尔排序方法又称为缩小增量排序，其基本思想是将待排序的记录划分成几组，从而减少参与直接插入排序的数据量，当经过几次分组排序后，记录的排列已经基本有序，这个时候再对所有的记录实施直接插入排序。
具体步骤可以描述如下：假设待排序的记录为n个，先取整数d 2. 希尔排序算法 (1) 分别让每个记录参与相应分组中的排序 若分为d组，前d个记录就应该分别构成由一个记录组成的有序段，从d+1个记录开始，逐一将每个记录a[i]插入到相应组中的有序段中，其算法可以这样实现： for （i=d+1; i<=n; i++) { 将a[i]插入到相应组的有序段中；} (2) 将a[i]插入到相应组的有序段中的操作可以这样实现： 将a[i]赋予a[0]中，即a[0]=a[i]; 让j指向a[i]所属组的有序序列中最后一个记录 搜索a[i]的插入位置 while(j>0 && a[0].key
