数据结构与算法——希尔、归并、快速排序
1. 回顾
前面说完了三种较为简单的排序算法，分别是冒泡排序，选择排序和插入排序，它们的平均情况时间复杂度都是 O(n2)，比较的高，适合小规模的数据排序，其中插入排序的效率稍高，所以更推荐使用插入排序。今天再来看看另外三种时间复杂度都是 O(nlogn) 的排序算法，分别是希尔排序、归并排序和快速排序。其中后两者的应用非常的广泛。
2. 希尔排序
先来看看希尔排序，它是较早突破 O(n2) 的时间复杂度的算法之一，其实是对插入排序的一种优化。前面说到的插入排序，操作非常的机械，就是按照固定顺序逐步比较大小，但是遇到一些比较极端的情况，数据移动的操作就会很频繁，比如排序数组 [3, 5, 1, 7, 9, 0] ，要将最后的 0 移动到最前面，几乎会遍历整个数组。
所以，希尔排序对此进行了优化，采用一种分组策略，来缩小数据的移动，使数组整体是基本有序的，小的在前，大的在后，然后缩小增量，这样数据的移动就会比较的少。
结合图来理解一下：
先将数组分为 4 组，分别进行插入排序，然后再分为 2 组，再进行插入排序。最后分为一组，即数组本身，因为此时数据已经基本上是有序的了，所以只需要进行微调即可。
下面是它的代码实现：
public class ShellSort {
public static void shellSort(int[] data) {
int length = data.length;
if (length <= 1) return;
//确定增量
int gap = length / 2;
while (gap >= 1){
for (int i = gap; i < length; i++) {
int value = data[i];
int j = i - gap;
for (; j >= 0; j -= gap){
if (data[j] > value) data[j + gap] = data[j];
else break;
}
data[j + gap] = value;
}
//更新增量
gap = gap / 2;
}
}
}希尔排序并没有很广泛的应用，原因是比起归并排序，它是不稳定的，比起快速排序，它的执行效率稍低。
3. 归并排序
归并排序大致分为两个步骤，一是拆分，二是合并。将数组拆分为许多小的数组，将小的数组排序了，然后合并为大数组。这种思想叫做分治，即将一个大的问题分解成小的问题来解决。用到分治思想的问题大多可以使用递归这种编程技巧。
下面是它的图展示：
结合图分析，假如我们要排序 data[p - r] 这个数组，可以先排序 data[p - q] 和 data[q+1 - r]，然后进行合并。用公式可以这样表示：
merge_sort(data[p - r]) = merge(merge_sort(data[p - q]), merge_sort(data[q+1 - r]));
其中 merge 函数的作用是将两个已排序的数组进行合并，那么 merge 函数该如何表示呢？
思路其实很简单，新建一个临时数组，分别从头开始扫描两个子数组，比较大小，将小的放入到临时数组中，然后指针向后移，继续比较。你可以结合归并排序的代码实现来理解：
public class MergeSort {
public static void mergeSort(int[] data) {
mergeInternally(data, 0, data.length - 1);
}
private static void mergeInternally(int[] data, int p, int r){
if (p >= r) return;
//计算p到r的中间值
int q = p + ((r - p) >> 1);
//递归分解
mergeInternally(data, p, q);
mergeInternally(data, q + 1, r);
//合并已排序数组
merge(data, p, q, r);
}
private static void merge(int[] data, int p, int q, int r){
int i = p;
int j = q + 1;
int k = 0;
//初始化一个临时数组
int[] temp = new int[r - p + 1];
while (i <= q && j <= r){
if (data[i] <= data[j]) temp[k ++] = data[i ++];
else temp[k ++] = data[j ++];
}
//判断哪个数组中有剩余的数据
int start = i;
int end = q;
if (j <= r){
start = j;
end = r;
}
//将剩余的数据拷贝到temp中
while (start <= end){
temp[k ++] = data[start ++];
}
//将temp拷贝到data中
for (int t = 0; t <= r - p; t ++) {
data[p + t] = temp[t];
}
}
}4. 快速排序
快速排序的思路和上面的归并排序很类似，都用到了分治的思想，在数组中选取一个分区点，将大于分区点的数放在右边，小于分区点放在左边。然后依次递归完成排序。
在归并排序中有一个 merge 合并函数，在快速排序中有一个 partition 分区函数，这个函数的主要功能是选取分区点，然后将大于分区点的数据放在右边，小的放在左边，返回分区点下标。实现这个函数的思路比较的巧妙：
对于数组 data[p - r]，我们选取最后一个数据 data[r] 作为分区点，用两个指针 i，j 都指向数组第一个元素，如果 data[j] < data[r]，交换 data[i] 和 data[j] 的位置，i 和 j 都向前移动。如果 data[j] > data[r]，则不交换，i 不动，j 向前移动，直至到达数组末尾。
对于分区点的选择，其实直接选择数组的最后一个元素是有问题的，在极端的情况下，数组本来就是有序的，那么每次分区都会遍历整个数组，时间复杂度就退化为 O(n2) 了。我们的理想是，大于分区点和小于分区点的数据是均匀分布的，不会出现太多或太少的情况。
这里提供了另外两种解决办法：一是三数取中法，就是取数组中的头、中、尾三个数，比较大小，取中间大小的数作为分区点。二是随机法，即随机选取一个数作为分区点。我下面的代码实现便是使用的三叔取中法。
public class QuickSort {
public static void quickSort(int[] data){
quickSortInternally(data, 0, data.length - 1);
}
private static void quickSortInternally(int[] data, int p, int r){
if (p >= r) return;
int q = partition(data, p, r);
quickSortInternally(data, p, q - 1);
quickSortInternally(data, q + 1, r);
}
private static int partition(int[] data, int p, int r) {
//三数取中法求pivot
int q = p + ((r - p) >> 1);
int mid = 0;
if ((data[p] - data[q]) * (data[q] - data[r]) >= 0) mid = q;
else if ((data[q] - data[p]) * (data[p] - data[r]) >= 0) mid = p;
else mid = r;
int pivot = data[mid];
//将pivot放到数组的末尾
swap(data, mid, r);
int i = p;
for (int j = p; j < r; j ++){
if (data[j] < pivot){
swap(data, i, j);
i ++;
}
}
swap(data, i, r);
return i;
}
private static void swap(int[] data, int i, int j){
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}5. 总结
这三种排序算法的平均时间复杂度都是 O(nlogn) ，归并排序和快速排序的应用更广泛。
希尔排序和快速排序是不稳定的，没有借助额外的存储空间，因此空间复杂度是 O(1) 。
归并排序是稳定的，使用了临时数组，大小和排序数组大小相同，因此空间复杂度是 O(n) 。