约定
待排序的元素需要实现 Java 的 Comparable 接口，该接口有 compareTo() 方法，可以用它来判断两个元素的大小关系。
使用辅助函数 less() 和 swap() 来进行比较和交换的操作，使得代码的可读性和可移植性更好。
排序算法的成本模型是比较和交换的次数。
public abstract class MySort<T extends Comparable<T>> {public abstract void sort(T[] nums);protected boolean less(T v, T w) {return v.compareTo(w) < 0;}protected void swap(T[] a, int i, int j) {T t = a[i];a[i] = a[j];a[j] = t;}}
选择排序
从数组中选择最小元素，将它与数组的第一个元素交换位置。再从数组剩下的元素中选择出最小的元素，将它与数组的第二个元素交换位置。不断进行这样的操作，直到将整个数组排序。
选择排序需要 ~N/2 次比较和 ~N 次交换，它的运行时间与输入无关，这个特点使得它对一个已经排序的数组也需要这么多的比较和交换操作。
public class Selection<T extends Comparable<T>> extends MySort<T> {
@Override
public void sort(T[] nums) {
int N = nums.length;
for (int i = 0; i < N - 1; i++) { // 因为内循环需要 i+1 ,所以就没必要遍历到 N ,遍历到 N-1 就行
int min = i;
for (int j = i + 1; j < N; j++) {
if (less(nums[j], nums[min])) {
min = j;
}
}
swap(nums, i, min);
}
}
}
插入排序
每次都将当前元素插入到左侧已经排序的数组中，使得插入之后左侧数组依然有序。
对于数组 {3, 5, 2, 4, 1}，它具有以下逆序：(3, 2), (3, 1), (5, 2), (5, 4), (5, 1), (2, 1), (4, 1)，插入排序每次只能交换相邻元素，令逆序数量减少 1，因此插入排序需要交换的次数为逆序数量。
插入排序的时间复杂度取决于数组的初始顺序，如果数组已经部分有序了，那么逆序较少，需要的交换次数也就较少，时间复杂度较低。
- 平均情况下插入排序需要 ~N/4 比较以及 ~N/4 次交换；
- 最坏的情况下需要 ~N/2 比较以及 ~N/2 次交换，最坏的情况是数组是倒序的；
- 最好的情况下需要 N-1 次比较和 0 次交换，最好的情况就是数组已经有序了。
// 这里实现的是交换式的插入排序;
// 就不实现移位式的了，理解复杂，面试也不问，懂原理就行。
public class Insertion<T extends Comparable<T>> extends MySort<T> {
@Override
public void sort(T[] nums) {
int N = nums.length;
for (int i = 1; i < N; i++) { // i 不从 0 开始，因为数组的第一个元素默认就是有序的了
for (int j = i; j > 0 && less(nums[j], nums[j - 1]); j--) { // j > 0 就行，不必等于 0 ,否则后面的 nums[j - 1] 可能会数组越界
swap(nums, j, j - 1);
}
}
}
}
希尔排序
对于大规模的数组，插入排序很慢，因为它只能交换相邻的元素，每次只能将逆序数量减少 1。希尔排序的出现就是为了解决插入排序的这种局限性，它通过交换不相邻的元素，每次可以将逆序数量减少大于 1。
希尔排序使用插入排序对间隔 h 的序列进行排序。通过不断减小 h，最后令 h=1，就可以使得整个数组是有序的。
/
// 会看就行，不必会敲
public class Shell<T extends Comparable<T>> extends MySort<T> {
@Override
public void sort(T[] nums) {
int N = nums.length;
int h = 1;
while (h < N / 3) {
h = 3 * h + 1; // 1, 4, 13, 40, ...
}
while (h >= 1) {
for (int i = h; i < N; i++) {
for (int j = i; j >= h && less(nums[j], nums[j - h]); j -= h) {
swap(nums, j, j - h);
}
}
h = h / 3;
}
}
}
希尔排序的运行时间达不到平方级别，使用递增序列 1, 4, 13, 40, … 的希尔排序所需要的比较次数不会超过 N 的若干倍乘于递增序列的长度。后面介绍的高级排序算法只会比希尔排序快两倍左右。
归并排序
1. 原地归并方法
下面的归并方法是将数组中两个已经排序的部分归并成一个。
// 归并数组中左右两边已经排好序的部分
public void merge(T[] nums, int l, int m, int h) {
int i = l, j = m + 1;
for (int k = l; k <= h; k++) {
aux[k] = nums[k]; // 将数据复制到辅助数组
}
// 将已经排好序的辅助数组的两边归并到原数组
for (int k = l; k <= h; k++) {
if (aux[i].compareTo(aux[j] <= 0)) { // 当左边的比右边的小，取左边的
nums[k] = aux[i++];
} else if (aux[i].compareTo(aux[j]) > 0) { // 当右边的比左边的大，取右边的
nums[k] = aux[j++];
} else if (i > m) { // 左边用完了
nums[k] = aux[j++];
} else if (j > h) { //右边用完了
nums[k] = aux[i++];
}
}
}
这是一种原地的归并方法，可以借助这种原地特性运用到递归中，实现递归的归并排序。
2. 自顶向下归并排序
将一个大数组分成两个小数组去求解。
因为每次都将问题对半分成两个子问题，这种对半分的算法复杂度一般为 O(NlogN)。
public class Up2DownMergeSort<T extends Comparable<T>> extends MySort<T> {
@Override
public void sort(T[] nums) {
aux = (T[]) new Comparable[nums.length];
sort(nums, 0, nums.length - 1);
}
// 递归调用原地归并方法实现归并
private void sort(T[] nums, int l, int h) {
if (h <= l) {
return;
}
int mid = (l + h) / 2;
sort(nums, l, mid);
sort(nums, mid + 1, h);
merge(nums, l, mid, h);
}
// 原地归并方法
public void merge(T[] nums, int l, int m, int h) {
int i = l, j = m + 1;
for (int k = l; k <= h; k++) {
aux[k] = nums[k]; // 将数据复制到辅助数组
}
// 将已经排好序的辅助数组的两边归并到原数组
for (int k = l; k <= h; k++) {
if (i > m) { // 左边用完了
nums[k] = aux[j++];
} else if (j > h) { //右边用完了
nums[k] = aux[i++];
} else if (aux[i].compareTo(aux[j] <= 0)) { // 当左边的比右边的小，取左边的
nums[k] = aux[i++];
} else if (aux[i].compareTo(aux[j]) > 0) { // 当右边的比左边的大，取右边的
nums[k] = aux[j++];
}
}
}
}
3. 自底向上归并排序
先归并那些微型数组，然后成对归并得到的微型数组。
public class Down2UpMergeSort<T extends Comparable<T>> extends MergeSort<T> {
@Override
public void sort(T[] nums) {
int N = nums.length;
aux = (T[]) new Comparable[N];
for (int sz = 1; sz < N; sz += sz) {
for (int lo = 0; lo < N - sz; lo += sz + sz) {
merge(nums, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1));
}
}
}
}
快速排序
1. 基本算法
- 归并排序将数组分为两个子数组分别排序，并将有序的子数组归并使得整个数组排序；
- 快速排序通过一个切分元素将数组分为两个子数组，左子数组小于等于切分元素，右子数组大于等于切分元素，将这两个子数组排序也就将整个数组排序了。
public class QuickSort<T extends Comparable<T>> extends MySort<T> {
private void shuffle(T[] nums) {
List<Comparable> list = Arrays.asList(nums);
Collections.shuffle(list);
list.toArray(nums);
}
@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 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 (j <= i)
break;
swap(nums, i, j);
}
swap(nums, l, j);
return j;
}
}
2. 切分
快排的精髓就是切分
**
切分的作用是只能确定切分元素在数组中的大小位置顺序；在切分元素左边的数虽然都比切分元素小，但它们并不是排好序的，右边同理！
取 a[l] 作为切分元素，然后从数组的左端向右扫描直到找到第一个大于等于它的元素，再从数组的右端向左扫描找到第一个小于它的元素，交换这两个元素。不断进行这个过程，就可以保证左指针 i 的左侧元素都不大于切分元素，右指针 j 的右侧元素都不小于切分元素。当两个指针相遇交叉时，将切分元素 a[l] 和 a[j] 交换位置。
// 使原先预设的最左侧的切分元素到达数组的正确位置并返回，以便下次切分的递归调用
private int partition(T[] nums, int l, int h) {
// 创建左右两个扫描索引
// 因为下面的 while 循环扫描是先 ++i --j 后才进行数值比较;
// 所以让 i = l 才能先从最左边的切分元素的第二个元素开始扫描(不必扫描切分元素);
// 让 j = h + 1 才能从数组最后一个元素开始扫描(不要把最后一个元素给漏了)。
int i = l, j = h + 1;
T cut = nums[l]; // 切分元素默认是第一个数
while (true) {
// 左扫描只要比切分元素小就一直循环扫描，直到发现比切分元素大的就退出循环;右扫描则相反
while (i != h && nums[++i] < cut) ;
while (j != l && nums[--j] > cut) ;
// 除开第一个切分元素
// 若后面有奇数个元素，则就会出现 i== j 的情况然后退出
// 若后面有偶数个元素，则就会出现 i > j 的情况，然后退出
if (i >= j)
break;
swap(nums, i, j);
}
// i 和 j 两个扫描指针相遇交叉退出后即可将切分元素放到正确的位置
swap(nums, l, j);
// 返回切分元素有序后的位置以便进行左递归切分和右递归切分
return j;
}
3. 性能分析
快速排序是原地排序，不需要辅助数组，但是递归调用需要辅助栈。
快速排序最好的情况下是每次都正好将数组对半分，这样递归调用次数才是最少的。这种情况下比较次数为 C=2C+N，复杂度为 O(NlogN)。
最坏的情况下，第一次从最小的元素切分，第二次从第二小的元素切分，如此这般。因此最坏的情况下需要比较 N/2。为了防止数组最开始就是有序的，在进行快速排序时需要随机打乱数组。
4. 算法改进
4.1 切换到插入排序
因为快速排序在小数组中也会递归调用自己，对于小数组，插入排序比快速排序的性能更好，因此在小数组中可以切换到插入排序。
4.2 三数取中
最好的情况下是每次都能取数组的中位数作为切分元素，但是计算中位数的代价很高。一种折中方法是取 3 个元素，并将大小居中的元素作为切分元素。
4.3 三向切分
对于有大量重复元素的数组，可以将数组切分为三部分，分别对应小于、等于和大于切分元素。
三向切分快速排序对于有大量重复元素的随机数组可以在线性时间内完成排序。
// 三向切分快速排序
public class ThreeWayQuickSort<T extends Comparable<T>> extends MySort<T> {
private void shuffle(T[] nums) {
List<Comparable> list = Arrays.asList(nums);
Collections.shuffle(list);
list.toArray(nums);
}
@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 lt = l, i = l + 1, gt = h; // 给lt i gt 设置初值
T v = nums[l]; // 切分元素
while (i <= gt) {
int cmp = nums[i].compareTo(v);
// nums[i] 等于 v 时，仅需要 i++
// nums[i] 大于 v 时，仅需要 gt-- ,但记得交换位置
// nums[i] 小于 v 时，需要 lt++ 和 i++ ,同时也要交换位置
if (cmp == 0) {
i++;
} else if (cmp > 0) {
swap(nums, i, gt--);
} else {
swap(nums, lt++, i++);
}
}
sort(nums, l, lt - 1);
sort(nums, gt + 1, h);
}
}
三向切分和二向切分不同：
二向切分会根据返回切分元素排好序后的位置，以便左递归二向切分和右递归二向切分得以调用。
// j 是排好序后的切分元素的位置 int j = partition(nums, l, h); // 左右递归需要依赖切分元素的位置 sort(nums, l, j - 1); sort(nums, j + 1, h);三向切分则是直接将与切分元素都相同的元素用一个区间 [ lt , gt ] 来表示，在进行左递归三向切分和右递归三向切分时，就不必根据切分元素返回后的位置来进行左右递归调用，而是直接根据区间来进行左右递归调用。
// 三向切分不需要依赖切分元素的位置 // 而是依赖与切分元素相同的所有元素的左右边界[ lt , gt ] 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。
这个快速选择算法也可以将整个数组排序：就是找出数组最大的元素就行了，数组自然而然的就会按照递增的方式进行快速排序，就是相当于快排了，**只要不返回值就行了**。
并且假如有些题目要找出形如前 k 小的元素，也是一样，直接传入 k 即可，数组就只会排序直到第 k+1 个切分元素的位置确定了就停止，那么前 K 个元素都比第 K+1 个元素小，那么这前 K 个元素就是我们要的答案，并且这前 K 个元素并不是排好序的！
所以把**快速选择算法和切分算法**的代码记住了，就可以做类似于 TopK 的各种变换题目了。
快速排序是将整个数组都排好序！
快速选择是确定数组下标为 K 的第 K+1 个元素的顺序，并且让数组下标为 K 的左边的元素都比其小，但不是排好序的，右边同理。**
public T quickSelect(T[] nums, int k) {
int l = 0, h = nums.length - 1;
while (l < h) {
int j = partition(nums, l, h);
if (k == j) {
return nums[k];
} else if (k < j) {
// k < 切分元素，说明 k 在切分元素的左边，将 high 值改变，进行下一次切分
h = j - 1;
} else {
// k > 切分元素，说明 k 在切分元素右边，将 low 值改变，进行下一次切分
l = j + 1;
}
}
return nums[k];
}
// 切分的代码，注释版在上面
public int partition(T[] nums, int l, int h) {
int i = l, j = h + 1;
T cut = nums[l];
while (true) {
while (i != h && nums[++i] < cut) ;
while (j != l && nums[--j] > cut) ;
// 下面这个 i >= j 是重点
if (i >= j)
break;
swap(nums, i, j);
}
swap(nums, l, j);
return j;
}
public swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
堆排序
1. 堆排序和优先队列的关系
优先队列是一种可以删除最大值和插入值的数据结构，可以用无序数组来实现也可以用堆（可用数组存储）来实现。
而堆排序就是利用了优先队列可以删除最大值并返回最大值的思想加以修改得来的。
堆排序是把最大值筛选出来然后放在数组最后的位置而不像优先队列一样将其删除，循环结束后就得到升序的有序序列了。
总结：堆排序是借鉴了优先队列的思想，但二者之间并没有实质上的关系。
2. 堆
堆中某个节点的值总是大于等于或小于等于其子节点的值（以下所有的堆都指的是大顶堆），并且堆是一颗完全二叉树，完全二叉树可以有奇数个节点也可以有偶数个节点（偶数个节点经常被我以为是不可以）。
堆可以用数组来表示，这是因为堆是完全二叉树，而完全二叉树很容易就存储在数组中。位置 k 的节点的父节点位置为 k/2，而它的两个子节点的位置分别为 2k 和 2k+1。这里不使用数组索引为 0 的位置，是为了更清晰地描述节点之间的位置关系。
3. 上浮和下沉
3.1 上浮
在堆中，当一个节点比父节点大，那么需要交换这个两个节点。交换后还可能比它新的父节点大，因此需要不断地进行比较和交换操作，把这种操作称为上浮。
private void swim(int k) {
while (k > 1 && less(k / 2, k)) {
swap(k / 2, k);
k = k / 2;
}
}
3.2 下沉
类似地，当一个节点比子节点来得小，也需要不断地向下进行比较和交换操作，把这种操作称为下沉。一个节点如果有两个子节点，应当与两个子节点中最大那个节点进行交换。
堆排序主要就是利用了下沉的操作。
private void sink(T[] nums, int k, int N) {
while (2 * k <= N) {
int j = 2 * k;
if (j < N && less(nums[j], nums[j + 1])) // j < N 得放在前面，否则会短路
j++;
if (!less(nums[k], nums[j])) // 若下沉过后新的 k 比 j 大了就表示构建堆完成了
break;
swap(nums, k, j);
k = j; // 原先的 k 下沉后记得索引变小，才可能继续执行下沉
}
}
3. 堆排序
把最大元素和当前堆中数组的最后一个元素交换位置，并且不删除它，那么就可以得到一个从尾到头的递减序列，从正向来看就是一个递增序列，这就是堆排序。
3.1 构建堆
无序数组建立堆最直接的方法是从左到右遍历数组进行上浮操作。
而一个更高效的方法则是从右至左进行下沉操作，如果一个节点的两个节点都已经是堆有序，那么进行下沉操作可以使得以这个节点为根节点的堆有序。叶子节点不需要进行下沉操作，可以忽略叶子节点的元素，因此只需要遍历一半的元素即可。
3.2 交换堆顶元素与最后一个元素
3.3 代码实现堆排序
// 简洁版本
public class HeapSort<T extends Comparable<T>> extends MySort<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);
}
}
/**
* 对传进来的父节点 k 的子堆进行构建
*/
private void sink(T[] nums, int k, int N) {
while (2 * k <= N) {
int j = 2 * k;
if (j < N && less(nums[j], nums[j + 1])) // j < N 得放在前面，否则会短路
j++;
if (!less(nums[k], nums[j]))
break;
swap(nums, k, j);
k = j;
}
}
}
// 注释版本
public class HeapSort<T extends Comparable<T>> extends MySort<T> {
/**
* 数组第 0 个位置不能有元素
*/
@Override
public void sort(T[] nums) {
int N = nums.length - 1;
// 第一次构建堆不需要从 k=1 开始
// 外层 for 循环表示从 k=N/2 的父节点开始构建子堆
// k=N/2 这个父节点构建完后进行递减切换到与之紧接着的上一个父节点进行构建子堆
// 直到 k=1 到达了根节点，由于之前 k=2 和 k=3 这两个父节点表示的子堆已经是有序堆了，
// 所以当 k=1 时，整个堆也就自然而然的是有序堆了，这也就是下沉操作的魅力所在，不用像上浮操作一样每一个节点都要遍历
for (int k = N / 2; k >= 1; k--)
sink(nums, k, N);
// 循环进行 交换堆顶元素与最后一个元素 以及 构建堆 的操作
while (N > 1) {
swap(nums, 1, N--);
sink(nums, 1, N); // 这里构建堆则要从 k=1 开始，以为大部分的子堆都已经是有序的了
}
}
/**
* 对传进来的父节点 k 的子堆进行构建
* 构建一次之后 k 变为 j ,也就是此时 k 在之前为 2k 的位置，继续循环构建其子堆
*/
private void sink(T[] nums, int k, int N) {
// 完全二叉树有单数个节点也有偶数个节点
// 所以 N 可能是单数也可能是偶数,所以 2k == N 也是存在的
// 2k == N 是第一次构建堆时的必要边界条件，没有了它的话，假如传进来的堆有偶数个节点，就不会进去循环了，直接退出，等于白给
while (2 * k <= N) {
int j = 2 * k;
// j < N 表示最大下标 N 比 2K 大，表示第一次构建堆时存在 2k+1 这个右子节点，才可以进行 2k+1 也就是下面的 j++ 的操作
// 如果写成j <= N 就可能会在第一次构建堆时发生数组越界
// 并且没有任何意义:右子节点不存在，那 k 这个根节点就只能与 2k 这个子节点交换位置了
if (j < N && less(nums[j], nums[j + 1])) // j < N 得放在前面，否则会短路
j++;
if (!less(nums[k], nums[j])) // 若下沉过后新的 k 比 j 大了就表示构建堆完成了
break;
swap(nums, k, j);
k = j; // 原先的 k 下沉后记得索引变小，才可能继续执行下沉
}
}
}
4. 分析
对于堆排序，由于要对 N 个节点进行下沉操作，因此复杂度为 NlogN。
堆排序是一种原地排序，没有利用额外的空间。
现代操作系统很少使用堆排序，因为它无法利用局部性原理进行缓存，也就是数组元素很少和相邻的元素进行比较和交换。
小结
1. 排序算法的比较
| 算法 | 稳定性 | 时间复杂度 | 空间复杂度 | 备注 |
|---|---|---|---|---|
| 选择排序 | × | N | 1 | |
| 冒泡排序 | √ | N | 1 | |
| 插入排序 | √ | N ~ N | 1 | 时间复杂度和初始顺序有关 |
| 希尔排序 | × | N 的若干倍乘于递增序列的长度 | 1 | 改进版插入排序 |
| 快速排序 | × | NlogN | logN | |
| 三向切分快速排序 | × | N ~ NlogN | logN | 适用于有大量重复主键 |
| 归并排序 | √ | NlogN | N | |
| 堆排序 | × | NlogN | 1 | 无法利用局部性原理 |
快速排序是最快的通用排序算法，它的内循环的指令很少，而且它还能利用缓存，因为它总是顺序地访问数据，缓冲就有可能命中，不像堆排序不在附件访问数据，缓存命中的概率大大降低。它的运行时间近似为 ~cNlogN，这里的 c 比其它线性对数级别的排序算法都要小。
使用三向切分快速排序，实际应用中可能出现的某些分布的输入能够达到线性级别，而其它排序算法仍然需要线性对数时间。
2. Java 的排序算法实现
Java 主要排序方法为 java.util.Arrays.sort()，对于原始数据类型使用三向切分的快速排序，对于引用类型使用归并排序。
若有收获，就点个赞吧
0 人点赞
