必须掌握的排序算法

冒泡，选择，插入

其中冒泡和选择一定 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 的放右边，相较于普通快排，对于相等区间的处理，更加简单易懂。

/**
 * 三路快排要点
 * 1. 三个分区，需要一个指针从左到右游走，根据基准值进行三区分割
 * 2. 每次把相等分区的左右边界返回
 */
function quickSort(arr, left, right) {
  if (left < right) {
    const [leftBorder, rightBorder] = partition(arr, left, right)
    quickSort(arr, left, leftBorder - 1)
    quickSort(arr, rightBorder + 1, right)
  }
}
function partition(arr, left, right) {
  const pivotIndex = left + Math.floor(Math.random(right - left + 1))
  const pivot = arr[pivotIndex]
  // 指针 p 从左到右依次遍历与基准值比较
  let p = left
  while (p <= right) {
    if (arr[p] === pivot) {
      p++
    } else if (arr[p] < pivot) {
      swap(arr, left, p)
      left++
      p++
    } else {
      swap(arr, right, p)
      right--
      // 此处 p 没移动是因为从 right 位置换过来的元素与pivot的关系还不清楚
    }
  }
  return [left, right]
}

普通的快速排序，也很有用，对于解决 topK 的问题衍生出快速选择算法，见 lc.215

function quickSort(arr, left, right) {
  if (left < right) {
    const pivotIndex = partition(arr, left, right)
    quickSort(arr, left, pivotIndex - 1)
    quickSort(arr, pivotIndex + 1, right)
  }
}
function partition(arr, left, right) {
  const pivotIndex = left + Math.floor(Math.random() * (right - left + 1))
  const pivot = arr[pivotIndex]
  // 基准值放到最左或最右，避免在循环中频繁判断指针是否指向的基准值（三路快排存在等于的区间就无需这一步）
  swap(arr, left, pivotIndex)

  let l = left + 1,
    r = right
  while (l <= r) {
    // 选择把与基准值相等的统一放到一个侧，不然在后续分割的时候就不在一起了
    // 这也是为什么选择 arr[l] <= pivot 而不是 arr[r] >= pivot, 因为在上方我们把基准值放到了最左边
    while (l <= r && arr[l] <= pivot) {
      l++
    }
    while (l <= r && arr[r] > pivot) {
      r--
    }
    if (l < r) {
      swap(arr, l, r)
    }
  }
  // 结束时，l 一定在比基准值大的位置，而 r 在小于等于基准值的位置，把基准值放到正确的位置并且返回新的分割index - r
  swap(arr, left, r)
  return r
}

堆排序

堆就是一组数字从左往右逐个填满二叉树，这就是满二叉树，也就是堆了。特殊的堆是大/小根堆，也叫优先队列。比如 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
}