1.1.7 排序技术

在排序技术方面，主要考查插入排序、选择排序、冒泡排序、快速排序和堆排序等方法。

1.插入排序

每次将一个待排序的数据元素插入到前面已经排好序的数列中的适当位置，使数列依然有序，直到待排序数据元素全部插入完为止。

例，使用插入排序对3、4、2、1、5按照从小到大的顺序排序。

排序过程分析：

2.选择排序

每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最前，直到全部待排序的数据元素排完。

例，使用选择排序对3、4、2、1、5按照从小到大的顺序排序。

排序过程分析：

3.冒泡排序

两两比较待排序数据元素的大小，发现两个数据元素的次序相反时即进行交换，直到没有反序的数据元素为止。

设想被排序的数组R[1..N]垂直竖立，将每个数据元素看成有重量的气泡，根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上“漂浮”，如此反复进行，直至最后任何两个气泡都是轻者在上、重者在下为止。

例，使用冒泡排序对3、4、2、1、5按照从小到大的顺序排序。

排序过程分析：

4.快速排序

在当前无序区R[1..H]中任取一个数据元素作为比较的“基准”（不妨记为X），用此基准将当前无序区划分为左右两个较小的无序区：R[1..I-1]和R[I+1..H]，且左边的无序子区中数据元素均小于等于基准元素，右边的无序子区中数据元素均大于等于基准元素，而基准X则位于最终排序的位置上，即R[1..I-1]≤X.Key≤R[I+1..H]（1≤I≤H），当R[1..I-1]和R[I+1..H]均非空时，分别对它们进行上述的划分过程，直至所有无序子区中的数据元素均已排序为止。

例如，使用快速排序对7、8、3、4、9、1进行从小到大的排序（仅写出第一趟的结果，以第一个元素为主）。

排序过程分析：

一般来说，在考试的时候，只问第一趟的结果，也就是以第一个元素为主排列的结果。

5.堆排序

堆排序是一树形选择排序，在排序过程中，将R[1..N]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲节点和孩子节点之间的内在关系来选择最小的元素。

N个元素的序列K1,K2,K3,…,KN称为堆，当且仅当该序列满足以下特性：

Ki≤K2i，Ki≤K2i+1（1≤i≤[N/2]）

堆实质上是满足如下性质的完全二叉树：树中任一非叶子节点的关键字均大于等于其孩子节点的关键字。

堆排序正是利用小根堆（或大根堆）来选取当前无序区中关键字最小（或最大）的记录实现排序的。我们不妨利用大根堆来排序。每一趟排序的基本操作是：将当前无序区调整为一个大根堆，选取关键字最大的堆顶记录，将它和无序区中的最后一个记录交换。这样，正好和直接选择排序相反，有序区是在原记录区的尾部形成并逐步向前扩大到整个记录区。

例如，使用堆排序对7、8、3、4、9、1进行从小到大的排序，仅写出第一趟排序的结果。

排序过程分析：

因为有6个数，首先取6/2=3，然后看看k3≤k6是否成立（此处没有k7），因为k3的值是3，而k6的值是1，显然不满足条件，要将k3和k6进行交换，就变成如下形式：

然后再看k2≤k4和k2≤k5是否成立。因为k2的值是8，k4的值是4，而k5的值是9，所以，将k2的值和k4的值交换，得到如下序列：

再看k1≤k2和k1≤k3，发现不满足，此时的k1要和k2与k3中最小的一个进行交换，所以得到序列如下：

堆建好了吗？检查每个位置是否满足上面的条件，答案是“没有”。因为此时k3≤k6又不成立了，所以要进行交换，得到如下的序列：

以上是第一趟排列的结果，如果要进行第二趟堆排序的话，就从剩下的4、3、8、9、7开始。

6.各种排序方法的比较

各种排序方法的比较如表1-1所示。

表1-1 各种排序算法的比较