快速排序
1. 基本算法
- 归并排序将数组分为两个子数组分别排序，并将有序的子数组归并使得整个数组排序；
- 快速排序通过一个切分元素将数组分为两个子数组，左子数组小于等于切分元素，右子数组大于等于切分元素，将这两个子数组排序也就将整个数组排序了。
public class QuickSort<T extends Comparable<T>> extends Sort<T> { @Override public void sort(T[] nums) { shuffle(nums); sort(nums, 0, nums.length - 1); } private void sort(T[] nums, int l, int h) { if (h <= l) return; int j = partition(nums, l, h); sort(nums, l, j - 1); sort(nums, j + 1, h); } private void shuffle(T[] nums) { List<Comparable> list = Arrays.asList(nums); Collections.shuffle(list); list.toArray(nums); } }
2. 切分
取 a[l] 作为切分元素，然后从数组的左端向右扫描直到找到第一个大于等于它的元素，再从数组的右端向左扫描找到第一个小于它的元素，交换这两个元素。不断进行这个过程，就可以保证左指针 i 的左侧元素都不大于切分元素，右指针 j 的右侧元素都不小于切分元素。当两个指针相遇时，将切分元素 a[l] 和 a[j] 交换位置。
private int partition(T[] nums, int l, int h) { int i = l, j = h + 1; T v = nums[l]; while (true) { while (less(nums[++i], v) && i != h) ; while (less(v, nums[--j]) && j != l) ; if (i >= j) break; swap(nums, i, j); } swap(nums, l, j); return j; }
3. 性能分析
快速排序是原地排序，不需要辅助数组，但是递归调用需要辅助栈。
快速排序最好的情况下是每次都正好将数组对半分，这样递归调用次数才是最少的。这种情况下比较次数为 CN=2CN/2+N，复杂度为 O(NlogN)。
最坏的情况下，第一次从最小的元素切分，第二次从第二小的元素切分，如此这般。因此最坏的情况下需要比较 N2/2。为了防止数组最开始就是有序的，在进行快速排序时需要随机打乱数组。
4. 算法改进
4.1 切换到插入排序
因为快速排序在小数组中也会递归调用自己，对于小数组，插入排序比快速排序的性能更好，因此在小数组中可以切换到插入排序。
4.2 三数取中
最好的情况下是每次都能取数组的中位数作为切分元素，但是计算中位数的代价很高。一种折中方法是取 3 个元素，并将大小居中的元素作为切分元素。
4.3 三向切分
对于有大量重复元素的数组，可以将数组切分为三部分，分别对应小于、等于和大于切分元素。
三向切分快速排序对于有大量重复元素的随机数组可以在线性时间内完成排序。
public class ThreeWayQuickSort<T extends Comparable<T>> extends QuickSort<T> { @Override protected void sort(T[] nums, int l, int h) { if (h <= l) { return; } int lt = l, i = l + 1, gt = h; T v = nums[l]; while (i <= gt) { int cmp = nums[i].compareTo(v); if (cmp < 0) { swap(nums, lt++, i++); } else if (cmp > 0) { swap(nums, i, gt--); } else { i++; } } sort(nums, l, lt - 1); sort(nums, gt + 1, h); } }
5. 基于切分的快速选择算法
快速排序的 partition() 方法，会返回一个整数 j 使得 a[l..j-1] 小于等于 a[j]，且 a[j+1..h] 大于等于 a[j]，此时 a[j] 就是数组的第 j 大元素。
可以利用这个特性找出数组的第 k 个元素。
该算法是线性级别的，假设每次能将数组二分，那么比较的总次数为 (N+N/2+N/4+..)，直到找到第 k 个元素，这个和显然小于 2N。
public T select(T[] nums, int k) { int l = 0, h = nums.length - 1; while (h > l) { int j = partition(nums, l, h); if (j == k) { return nums[k]; } else if (j > k) { h = j - 1; } else { l = j + 1; } } return nums[k]; }
堆排序
1. 堆
堆中某个节点的值总是大于等于或小于等于其子节点的值，并且堆是一颗完全二叉树。
堆可以用数组来表示，这是因为堆是完全二叉树，而完全二叉树很容易就存储在数组中。位置 k 的节点的父节点位置为 k/2，而它的两个子节点的位置分别为 2k 和 2k+1。这里不使用数组索引为 0 的位置，是为了更清晰地描述节点的位置关系。
public class Heap<T extends Comparable<T>> { private T[] heap; private int N = 0; public Heap(int maxN) { this.heap = (T[]) new Comparable[maxN + 1]; } public boolean isEmpty() { return N == 0; } public int size() { return N; } private boolean less(int i, int j) { return heap[i].compareTo(heap[j]) < 0; } private void swap(int i, int j) { T t = heap[i]; heap[i] = heap[j]; heap[j] = t; } }
2. 上浮和下沉
在堆中，当一个节点比父节点大，那么需要交换这个两个节点。交换后还可能比它新的父节点大，因此需要不断地进行比较和交换操作，把这种操作称为上浮。
private void swim(int k) { while (k > 1 && less(k / 2, k)) { swap(k / 2, k); k = k / 2; } }
类似地，当一个节点比子节点来得小，也需要不断地向下进行比较和交换操作，把这种操作称为下沉。一个节点如果有两个子节点，应当与两个子节点中最大那个节点进行交换。
private void sink(int k) { while (2 * k <= N) { int j = 2 * k; if (j < N && less(j, j + 1)) j++; if (!less(k, j)) break; swap(k, j); k = j; } }
3. 插入元素
将新元素放到数组末尾，然后上浮到合适的位置。
public void insert(Comparable v) { heap[++N] = v; swim(N); }
4. 删除最大元素
从数组顶端删除最大的元素，并将数组的最后一个元素放到顶端，并让这个元素下沉到合适的位置。
public T delMax() { T max = heap[1]; swap(1, N--); heap[N + 1] = null; sink(1); return max; }
5. 堆排序
把最大元素和当前堆中数组的最后一个元素交换位置，并且不删除它，那么就可以得到一个从尾到头的递减序列，从正向来看就是一个递增序列，这就是堆排序。
5.1 构建堆
无序数组建立堆最直接的方法是从左到右遍历数组进行上浮操作。一个更高效的方法是从右至左进行下沉操作，如果一个节点的两个节点都已经是堆有序，那么进行下沉操作可以使得这个节点为根节点的堆有序。叶子节点不需要进行下沉操作，可以忽略叶子节点的元素，因此只需要遍历一半的元素即可。
5.2 交换堆顶元素与最后一个元素
交换之后需要进行下沉操作维持堆的有序状态。
public class HeapSort<T extends Comparable<T>> extends Sort<T> { /** * 数组第 0 个位置不能有元素 */ @Override public void sort(T[] nums) { int N = nums.length - 1; for (int k = N / 2; k >= 1; k--) sink(nums, k, N); while (N > 1) { swap(nums, 1, N--); sink(nums, 1, N); } } private void sink(T[] nums, int k, int N) { while (2 * k <= N) { int j = 2 * k; if (j < N && less(nums, j, j + 1)) j++; if (!less(nums, k, j)) break; swap(nums, k, j); k = j; } } private boolean less(T[] nums, int i, int j) { return nums[i].compareTo(nums[j]) < 0; } }
6. 分析
一个堆的高度为 logN，因此在堆中插入元素和删除最大元素的复杂度都为 logN。
对于堆排序，由于要对 N 个节点进行下沉操作，因此复杂度为 NlogN。
堆排序是一种原地排序，没有利用额外的空间。
现代操作系统很少使用堆排序，因为它无法利用局部性原理进行缓存，也就是数组元素很少和相邻的元素进行比较和交换。
小结
1. 排序算法的比较
| 算法 | 稳定性 | 时间复杂度 | 空间复杂度 | 备注 |
| 选择排序 | × | N2 | 1 | |
| 冒泡排序 | √ | N2 | 1 | |
| 插入排序 | √ | N ~ N2 | 1 | 时间复杂度和初始顺序有关 |
| 希尔排序 | × | N 的若干倍乘于递增序列的长度 | 1 | 改进版插入排序 |
| 快速排序 | × | NlogN | logN | |
| 三向切分快速排序 | × | N ~ NlogN | logN | 适用于有大量重复主键 |
| 归并排序 | √ | NlogN | N | |
| 堆排序 | × | NlogN | 1 | 无法利用局部性原理 |
快速排序是最快的通用排序算法，它的内循环的指令很少，而且它还能利用缓存，因为它总是顺序地访问数据。它的运行时间近似为 ~cNlogN，这里的 c 比其它线性对数级别的排序算法都要小。
使用三向切分快速排序，实际应用中可能出现的某些分布的输入能够达到线性级别，而其它排序算法仍然需要线性对数时间。
2. Java 的排序算法实现
Java 主要排序方法为 java.util.Arrays.sort()，对于原始数据类型使用三向切分的快速排序，对于引用类型使用归并排序。
