Published on

必须掌握的排序算法

Authors

冒泡,选择,插入

其中冒泡和选择一定 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)
        }
    }
}

递归时间复杂度估算

  1. 数学归纳法
  2. 主定理 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)

主定理给出了这类递归式时间复杂度的上界。但请注意,主定理并不适用于所有类型的递归式,有时可能需要配合其他方法。

  1. 对于树,一般用递归树法:将递归过程表示为一棵树,每个节点表示一个子问题的解,通过分析树的层数和每层的节点数来确定时间复杂度。

归并排序

分治思想,就是把数看成二叉树,然后从底往上合并(发挥想象力~)。

既然是从底往上合并,想来应该是后序遍历的递归了。

/**
 * 归并排序
 *
 * @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
}