必须掌握的排序方法&递归时间复杂度
系列 -
目录
冒泡，选择，插入
其中冒泡和选择一定 O(n^2)，插入最坏 O(N^2)，最好 O(N) 取决于数据结构。
// 测试数组
int[] arr = new int[]{2, 1, 5, 9, 5, 4, 3, 6, 8, 9, 6, 7, 3, 4, 2, 7, 1, 8};
/**
* 交换数组的两个值，此种异或交换值方法的前提是 i != j，否则会变为 0
*/
public void swap(int[] arr, int i, int j) {
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
// 保险还是用这个吧～
public void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}冒泡
从左往右，两两比较，冒出极值
public void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
boolean sorted = true; // 用于优化 提前终止
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
sorted = false;
}
}
if (sorted) break;
}
}function bubble(arr) {
for (let i = 0; i < arr.length - 1; i++) {
let sorted = true
for (let j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1)
sorted = false
}
}
if (sorted) break
}
}选择
选择每个数作为极值（最大/最小），然后去和其之后的数比较，更新极值的指针，最后交换
public void selectSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) {
swap(arr, minIndex, i);
}
}
}function select(arr) {
for (let i = 0; i < arr.length; ++i) {
let minIndex = i
for (let j = i + 1; j < arr.length; ++j) {
if (arr[minIndex] > arr[j]) {
minIndex = j
}
}
if (minIndex !== i) swap(arr, minIndex, i)
}
}插入
构建有序数列，从后往前找准位置插入
public static void insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; --j) {
swap(arr, j, j + 1);
}
}
}function insert(arr) {
for (let i = 1; i < arr.length; ++i) {
for (let j = i - 1; j >= 0 && arr[j] > arr[j + 1]; --j) {
swap(arr, j, j + 1)
}
}
}递归时间复杂度估算
- 数学归纳法
- 主定理 master 公式：
T(N) = a * T(N/b) + O(N^c)，a ≥ 1，b > 1；是一种用于求解分治算法时间复杂度的方法
-
T(N): 母问题体量
-
a，表示子问题被调了多少次
-
b，等量子问题的体量
-
O(N^c)：表示其他部分的时间复杂度
-
当 log_b(a) > c，则 O(n^log_b(a))
-
当 log_b(a) = c，则 O(n^c*logn)
-
当 log_b(a) < c，则 O(n^c)
主定理给出了这类递归式时间复杂度的上界。但请注意，主定理并不适用于所有类型的递归式，有时可能需要配合其他方法。
- 对于树，一般用递归树法：将递归过程表示为一棵树，每个节点表示一个子问题的解，通过分析树的层数和每层的节点数来确定时间复杂度。
归并排序
分治思想，就是把数看成二叉树，然后从底往上合并（发挥想象力～）。
既然是从底往上合并，想来应该是后序遍历的递归了。
/**
* 归并排序
*
* @param arr
* @param left
* @param right
*/
public void mergeSort(int[] arr, int left, int right) {
if (left == right) return; // 结束条件
int mid = left + (right - left >> 1);
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
public void merge(int[] arr, int left, int mid, int right) {
int[] help = new int[right - left + 1];
int p1 = left;
int p2 = mid + 1;
int i = 0;
while (p1 <= mid && p2 <= right) {
help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= mid) {
help[i++] = arr[p1++];
}
while (p2 <= right) {
help[i++] = arr[p2++];
}
for (int j = 0; j < help.length; j++) {
arr[left + j] = help[j];
}
}function mergeSort(arr, l, r) {
if (l == r) return
const mid = l + ((r - l) >> 1)
mergeSort(arr, l, mid) // 细节 分区的时候 [l..mid] [mid+1..r]，如过 [l..mid-1] [mid, r] 则可能死循环 012， 1，,2
mergeSort(arr, mid + 1, r)
merge(arr, l, mid, r)
}
function merge(arr, l, mid, r) {
const help = [] // size 为 r-l+1
let i = l
let j = mid + 1
let p = 0
while (i <= mid && j <= r) {
help[p++] = arr[i] < arr[j] ? arr[i++] : arr[j++]
}
while (i <= mid) {
help[p++] = arr[i++]
}
while (j <= r) {
help[p++] = arr[j++]
}
for (let k = 0; k < help.length; k++) {
arr[l + k] = help[k]
}
}来算下一下时间复杂度吧：根据 master 公式：T(N) = a * T(N/b) + O(N^c)，看代码中 mergeSort 内有两个地方调用自己，所以 a == 2，N 被等分了，所以 b == 2，其他地方 merge 函数的时间复杂度是 O(N)，所以 c == 1，那么我们看：log(b,a): log 以 b 为底 a 的对数，log(2,2) == 1 == c，所以时间复杂度是：O(N^c * logN) 即 O(NlogN)。
归并排序的思想过程可以帮助解决很多问题，比如小和问题和逆序对问题。
小和问题
一个数组中，每一个数左边比当前数小的数加起来的和就是这个数组的小和。比如：[1,3,4,2,5]，小和为：0 + 1 + 4 + 1 + 10 == 16。请你写一个算法求小和。
这道题需要转变一下思想：也可以看成每个数右侧有几个比它大：1 * 4 + 3 * 2 + 4 * 1 + 2 * 1 = 16。那么就可以考虑归并排序啦。
/**
* 归并排序
*
* @param arr
* @param left
* @param right
*/
public int mergeSort(int[] arr, int left, int right) {
if (left == right) return 0; // 结束条件
int mid = left + (right - left >> 1);
return mergeSort(arr, left, mid)
+ mergeSort(arr, mid + 1, right)
+ merge(arr, left, mid, right);
}
public int merge(int[] arr, int left, int mid, int right) {
int[] help = new int[right - left + 1];
int p1 = left;
int p2 = mid + 1;
int i = 0;
int res = 0; // 小和计算
while (p1 <= mid && p2 <= right) {
res += arr[p1] < arr[p2] ? arr[p1] * (right - p2 + 1) : 0; // 关键点
help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= mid) {
help[i++] = arr[p1++];
}
while (p2 <= right) {
help[i++] = arr[p2++];
}
for (int j = 0; j < help.length; j++) {
arr[left + j] = help[j];
}
return res;
}逆序对
一个数组中，左边的数如果比右边的数大，则两个数构成一个逆序对，请打印所有逆序对。这个跟小和问题异曲同工，就不多介绍了。
快速排序
荷兰国旗问题
荷兰国旗三色，其实就是一个简单的分区问题，一组数，把小于 target 的放一组，等于 target 的放中间，大于 target 的放右边。
要求：额外空间复杂度 O(1)，时间复杂度 O(N)。
/**
* 荷兰国旗问题，可以想象游标卡尺的两端往中间挤；
*
* @param arr
* @param target
*/
public static void partition(int[] arr, int target) {
int l = 0;
int r = arr.length - 1;
int i = 0;
while (i <= r) {
if (arr[i] < target) {
swap(arr, i, l);
i++;
l++;
} else if (arr[i] == target) {
i++;
} else {
swap(arr, i, r);
r--;
}
}
}快速排序实现
荷兰国旗的问题是快速排序的一环。
随机选择一个数作为 pivot，把 < pivot 的放左边， = pivot 的放中间，> pivot 的放右边。这也就是三路快排的基础。
function quickSort(arr, l, r) {
if (l >= r) return
const [lb, rb] = partition(arr, l, r)
quickSort(arr, l, lb - 1)
quickSort(arr, rb + 1, r)
}
function partition(arr, l, r) {
const pivotIndex = Math.floor(Math.random() * (r - l + 1)) + l
const pivot = arr[pivotIndex]
// swap(arr, pivotIndex, l) // 这一步是为了增加程序的鲁棒性，有没有结果都一样
let left = l
let right = r
let i = l
while (i <= right) {
if (arr[i] === pivot) {
i++
} else if (arr[i] < pivot) {
swap(arr, i++, left++)
} else {
swap(arr, i, right--)
}
}
return [left, right]
}
quickSort(arr, 0, arr.length - 1)/**
* 快速排序
*
* @param arr
* @param l
* @param r
*/
public void quickSort(int[] arr, int l, int r) {
if (l < r) {
// 随机选择一个数，把它作为基准，同时把它和最右边的数交换，然后进行分区
int pivot = l + (int) (Math.random() * (r - l + 1));
swap(arr, pivot, r);
// 返回 荷兰国旗的 <区右边界下一个 和 >区左边界上一个 即等于区域的[左右边界]
// 意味着：等于区域已经排好序了，对剩下的左右区域再分别排序即可
int[] p = partition(arr, l, r);
quickSort(arr, l, p[0] - 1);
quickSort(arr, p[1] + 1, r);
}
}
/**
* 快速排序分区 partition 函数
*
* @param arr
* @param l
* @param r
* @return 等于pivot的左右边界，闭区间
*/
private int[] partition(int[] arr, int l, int r) {
int left = l - 1; // < 区右边界
int right = r; // > 区左边界，因为 r 位置为基准值
// l 表示当前数位置
// 这里 小于 right 的原因是因为此时的 arr[r] 为基准值，不需要参与分区过程中
// 在分区完毕后，放到正确的位置即可
while (l < right) {
if (arr[l] < arr[r]) {
swap(arr, ++left, l++);
} else if (arr[l] == arr[r]) {
l++;
} else {
swap(arr, l, --right);
}
}
swap(arr, l, r); // 最终 l == right，基准值归位
return new int[]{left + 1, right}; // 因为最后r回归到等于它的位置
}快速排序变体算法 —
快速选择算法 ==> 快速排序 + 二分的思想，见 lc.215
堆排序
堆就是一组数字从左往右逐个填满二叉树，这就是满二叉树，也就是堆了。特殊的堆是大/小根堆，也叫优先队列。比如 React 的底层就用了小根堆，java 中的 PriorityQueue 默认也是小根堆，可以传入比较器来控制。
节点关系
- 左子节点：2*i + 1
- 右子节点：2*i + 2
- 父节点：(i - 1)/2，注意：java 中可以这么做因为 java 中 -1 / 2 == 0；js 中就可以使用绝对值和位运算来简化操作。
上浮和下沉
上浮就是当数字一个一个进入堆中，从最后往上走，构建出大/小根堆。
/**
* 上浮操作：一组数，逐个插入堆中，形成大/小根堆，时间复杂度O(logn)
*/
public void shiftUp(int[] arr, int index) {
while (arr[index] > arr[(index - 1) / 2]) { // 子大于父 就交换 （大根堆）
swap(arr, index, (index - 1) / 2);
index = (index - 1) / 2;
}
}
/**
* 建堆，注意时间复杂度是 O(nlogn)
*/
int[] data = new int[]{3, 1, 2, 3, 8, 6, 6, 4, 9, 3, 7};
for (int i = 0; i < data.length; i++) {
shiftUp(data, i);
}下沉一般是在堆顶出堆后（与最后一个交换），
/**
* @param arr
* @param index
* @param heapSize，传size是为了方便当出堆的时候，重新建堆
*/
public void shiftDown(int[] arr, int index, int heapSize) {
int left = 2 * index + 1;
while (left < heapSize) { // 证明存在子节点
int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left; // 左右孩子中较大的那个
largest = arr[largest] > arr[index] ? largest : index; // 较大的子 与 父 比更大的那个
if (largest == index) {
break;
}
swap(arr, largest, index);
index = largest;
left = 2 * index + 1;
}
}注意：一个数一个数加入堆中上浮的方式建堆的时间复杂度是 O(nlogn)，一般我们也可以直接对 n/2 的数据进行下沉操作来进行优化，整体时间复杂度是 O(n)。
int[] data = new int[]{3, 1, 2, 3, 8, 6, 6, 4, 9, 3, 7};
for (int i = data.length / 2; i >= 0; --i) {
shiftDown(data, i, data.length);
}时间复杂度证明：
- T(n) = n/2 * 1 + n/4 * 2 + n/8 * 3 + …
- 2T(n) = n/2 * 2 + n/2 * 2 + n/4 * 3 + …
错位相减： T(n) = n + n/2 + n/4 + n/8 + ...， 等比数列求和公式：sn = an。所以时间复杂度是 O(n)。
堆排序实现
有了上浮和下沉的 api，堆排序就是堆顶不断出堆的过程。（堆顶与最后一个交换，同时减少 heap 的 size，从头部 shiftDown 重新建堆）
public void heapSort(int[] arr) {
// 初始建堆
for (int i = arr.length / 2; i >= 0; --i) {
shiftDown(arr, i, arr.length);
}
// 进行排序
int heapSize = arr.length;
for (int i = arr.length - 1; i >= 0; --i) {
swap(arr, 0, i);
heapSize--;
shiftDown(arr, 0, heapSize); // 不断与最后一个数字切断连接，对0位置重新建堆；
}
}function shiftDown(arr, index, heapSize) {
let left = 2 * index + 1
while (left < heapSize) {
// 注意边界条件 left + 1 < heapSize，因此，三元不等式不能写成 arr[left] < arr[left+1] ? left : left + 1
let minIndex = left + 1 < heapSize && arr[left + 1] < arr[left] ? left + 1 : left
minIndex = arr[index] < arr[minIndex] ? index : minIndex
if (arr[index] <= arr[minIndex]) {
break
}
swap(arr, index, minIndex)
index = minIndex
left = 2 * index + 1
}
}
function heapSort(arr) {
for (let i = arr.length >> 1; i >= 0; --i) {
shiftDown(arr, i, arr.length)
}
let n = arr.length
for (let i = n - 1; i >= 0; --i) {
swap(arr, 0, i)
n--
shiftDown(arr, 0, n)
}
}几乎有序的数组排序，建议使用堆排序
希尔排序
插入排序的升级版，也叫缩小增量排序，用 gap 分组，没每个组内进行插入排序，当 gap 为 1 时，就排好序了，相比插入排序多了设定 gap 这一层最外部 for 循环
function shellSort(nums) {
for (let gap = arr.length >> 1; gap > 0; gap >>= 1) {
// 多了设定gap增量这一层
for (let i = gap; i < arr.lenght; i++) {
let curr = i
let temp = nums[i]
while (curr - gap >= 0 && nums[curr - gap] > temp) {
nums[curr] = nums[curr - gap]
curr -= gap
}
nums[curr] = temp
}
}
}稳定性
稳定性就是相同的数字在排序后仍然保持着相对的位置。这种特性还是比较重要的，比如对一个年级的学生，先按照成绩排序，再按照班级排序。
冒泡选择和插入只有选择排序是不稳定的，因为在它的过程中，会把 min 或 max 与后面的交换，同理快速排序也不是稳定的，堆排序更不用提了~
- 快速排序: 时间 O(nlogn), 空间 O(logn)，相对而言速度最快
- 归并排序: 时间 O(nlogn)，空间 O(n)，具有稳定性
- 堆排序的：时间 O(nlogn)，空间 O(1)，空间最少
非比较排序
非比较排序往往都是牺牲空间换取时间，所以通常是需要数据结构满足一定的条件下才会去使用的。
计数排序
计数排序一般适合于样本空间不大的正整数排序，比如人的年龄，一定大于 0 小于 200。（当然对于负数咱可以通过 + 一个数让所有的数都变成正数后再排序, 排序完成后再减去）
核心：将数据作为另一个数组的键存储到另一个数组中，所以一般来说只针对正整数，当然咱可以通过 + 一个数让所有的数都变成正数后再排序, 排序完成后再减去。
/**
* 计数排序
*
* @param arr
* @param k
*/
public static void countSort(int[] arr, int k) {
int[] count = new int[k + 1];
for (int i = 0; i < arr.length; i++) {
count[arr[i]] += 1;
}
int[] bucket = new int[arr.length];
// 构建计数尺子的前缀和,统计频率，基数排序也会用到这种。
// 现在: count[i] 的含义为 arr 中 <= i 的数字有多少个
for (int i = 1; i < count.length; i++) {
count[i] += count[i - 1];
}
// 从右往左遍历原数组，根据count统计的频率进行排序
// 从右往左是为了保证稳定性
for (int i = arr.length - 1; i >= 0; --i) {
bucket[count[arr[i]] - 1] = arr[i];
count[arr[i]]--;
}
for (int i = 0; i < bucket.length; i++) {
arr[i] = bucket[i];
}
}时间复杂度 O(n + k)： n 个数, k 为范围。
基数排序
基数排序比计数排序的使用范围更加广一点，因为是根据每个进位来产生桶，最多也就 0-9 十个桶。
相对于计数排序，根据进位，多次入桶。
public static void main(String[] args) {
// 这个数据的范围就是 0 ～ 13
int[] data = new int[]{4, 5, 1, 8, 13, 0, 9, 200};
int maxBit = maxBit(data);
radixSort(data, 0, data.length - 1, maxBit);
System.out.println(Arrays.toString(data));
}
/**
* 基数排序
*/
public static void radixSort(int[] arr, int l, int r, int maxBit) {
final int radix = 10; // 基数 0 ～ 9 一共10位
int i = 0, j = 0;
int[] bucket = new int[r - l + 1]; // 桶的大小和原数组一样大小
for (int d = 0; d < maxBit; d++) { // 对每个进行进行单独遍历入桶、出桶
int[] count = new int[radix];
// 进行基数统计
for (i = l; i <= r; i++) {
j = getDigit(arr[i], d);
count[j]++;
}
// 求前缀和
for (i = 1; i < count.length; i++) {
count[i] += count[i - 1];
}
// 从右向左遍历原数组，根据前缀和找到它对应的位置，入桶
for (i = r; i >= l; --i) {
j = getDigit(arr[i], d);
bucket[count[j] - 1] = arr[i];
count[j]--;
}
// 出桶还原到原数组
for (i = l, j = 0; i <= r; i++, j++) {
arr[i] = bucket[j];
}
}
}
/**
* 找到最大数有多少位
*/
public static int maxBit(int[] arr) {
int max = Integer.MIN_VALUE;
for (int digit : arr) {
max = Math.max(max, digit);
}
int bit = 0;
while (max != 0) {
bit++;
max = max / 10;
}
return bit;
}
/**
* 取出数x进位d上的数字
*
* @param x
* @param d
* @return
*/
public static int getDigit(int x, int d) {
return (x / (int) Math.pow(10, d)) % 10;
}桶排序
前提：假设输入数据服从均匀分布。
它利用函数的映射关系，将待排序元素分到有限的桶里，然后桶内元素再进行排序（可能是别的排序算法），最后将各个桶内元素输出得到一个有序数列
时间复杂度 O(n)
function bucketSort(nums) {
// 先确定桶的数量，要找出最大最小值，再根据 scope 求出桶数
const scope = 3 // 每个桶的存储的范围
const min = Math.min(...nums)
const max = Math.max(...nums)
const count = Math.floor((max - min) / scope) + 1
const bucket = Array.from(new Array(count), _ => [])
// 遍历数据，看应该放入哪个桶中
for (const value of nums) {
const index = ((value - min) / scope) | 0
bucket[index].push(value)
}
const res = []
// 对每个桶排序 然后放入结果集
for (const item of bucket) {
insert(item) // 插入排序
res.push(...item)
}
return res
}