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) 。
![现有一个接口DataOperation定义了排序方法sort(int[])和查找方法search(int[],int)，已知类QuickSort的quickSort(int[])方法实现了快速排序算法](https://ucc.alicdn.com/b3c447iaqrtq2_20240813_8507e56fc1e0475c88702b767789ed11.png?x-oss-process=image/resize,h_160,m_lfit)