排序 · SkyBlog

下面都是将整数数组排序为升序

// 使用到的原地交换方法
const swap = (nums: number[], i: number, j: number) => {
  ;[nums[i], nums[j]] = [nums[j], nums[i]]
}

冒泡排序（Bubble Sort）

通过连续地比较与交换相邻元素实现排序。这个过程就像气泡从底部升到顶部一样，因此得名冒泡排序。

const bubbleSort = (nums: number[]) => {
  for (let i = nums.length - 1; i > 0; i--) {
    for (let j = 0; j < i; j++) {
      if (nums[j] > nums[j + 1]) {
        swap(nums, j, j + 1)
      }
    }
  }
}

选择排序（Selection Sort）

从未排序区间查找最小的元素，将其放到已排序区间的末尾。

const selectionSort = (nums: number[]) => {
  for (let i = 0; i < nums.length - 1; i++) {
    let k = i
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[j] < nums[k]) {
        k = j
      }
    }
    swap(nums, i, k)
  }
}

插入排序（Insertion Sort）

逐个将元素插入已排序部分，形成新的有序列表。

const insertionSort = (nums: number[]) => {
  for (let i = 1; i < nums.length; i++) {
    const base = nums[i]
    let j = i - 1
    while (j >= 0 && nums[j] > base) {
      nums[j + 1] = nums[j]
      j--
    }
    nums[j + 1] = base
  }
}

快速排序（Quick Sort）

选择一个基准元素，将列表分为两个子列表，小于基准的放在左边，大于基准的放在右边，然后对两个子列表递归地应用相同的方法。

// 交换元素使返回索引 i 满足 nums[a] <= nums[i] <= nums[b] (a∈[left,i]; b∈[i,right]; nums[i]==nums[left])
const partition = (nums: number[], left: number, right: number): number => {
  // 以 nums[left] 为基准数；优化可以先选择几个数把中位数交换到 left 位置上，使交换后左右数量尽可能平均
  let [i, j] = [left, right]
  while (i < j) {
    while (i < j && nums[j] >= nums[left]) j-- // 这两个 while 在这种含等号循环条件下不能交换顺序；
    while (i < j && nums[i] <= nums[left]) i++ // 因为外层 while 循环结束时（i==j)，还会交换 nums[left] 与 nums[i]，需满足 nums[i] <= nums[left] 才行
    swap(nums, i, j)
  }
  swap(nums, left, i)
  return i
}
 
const quickSort = (nums: number[], left: number, right: number) => {
  if (left >= right) return
  const pivot = partition(nums, left, right)
  quickSort(nums, left, pivot - 1)
  quickSort(nums, pivot + 1, right)
}

三路快排

const partition = (nums: number[], left: number, right: number): [number, number] => {
  let [l, r, i] = [left, right, left + 1]
  const pivot = nums[left]
  while (i <= r) {
    if (nums[i] < pivot) swap(nums, i++, l++)
    else if (nums[i] > pivot) swap(nums, i, r--)
    else i++
  }
  return [l, r]
}
 
const quickSort3Way = (nums: number[], left: number, right: number) => {
  if (left >= right) return
  const [l, r] = partition(nums, left, right)
  quickSort3Way(nums, left, l - 1)
  quickSort3Way(nums, r + 1, right)
}

归并排序（Merge Sort）

一种基于分治策略的排序算法：

划分阶段：通过递归不断地将数组从中点处分开，将长数组的排序问题转换为短数组的排序问题。
合并阶段：当子数组长度为 1 时终止划分，开始合并，持续地将左右两个较短的有序数组合并为一个较长的有序数组，直至结束。

const merge = (nums: number[], left: number, mid: number, right: number) => {
  const tmp = new Array<number>(right - left + 1)
  let [i, j, k] = [left, mid + 1, 0]
  while (i <= mid && j <= right) tmp[k++] = nums[i] <= nums[j] ? nums[i++] : nums[j++]
  // 将左子数组和右子数组的剩余元素复制到临时数组中
  while (i <= mid) tmp[k++] = nums[i++]
  while (j <= right) tmp[k++] = nums[j++]
  // 将临时数组 tmp 中的元素复制回原数组 nums 的对应区间
  for (k = 0; k < tmp.length; k++) nums[left + k] = tmp[k]
}
 
const mergeSort = (nums: number[], left: number, right: number) => {
  if (left >= right) return
  const mid = (left + right) >> 1
  mergeSort(nums, left, mid)
  mergeSort(nums, mid + 1, right)
  merge(nums, left, mid, right)
}

堆排序（Heap Sort）

利用堆数据结构，将列表转换为最大堆（最小堆），然后每次从堆顶取出最大（最小）元素，重新调整堆结构。

// 堆的长度为 len，从节点 i 开始，从顶至底堆化
const ajustHeap = (nums: number[], i: number, len: number) => {
  while (true) {
    const [l, r] = [2 * i + 1, 2 * i + 2] // 左右节点索引
    let max = i // 记录根与左右子节点中最大值的索引
    if (l < len && nums[l] > nums[max]) max = l
    if (r < len && nums[r] > nums[max]) max = r
    // 若节点 i 最大或索引 l, r 越界，则无须继续堆化，跳出
    if (max == i) break
    swap(nums, i, max)
    i = max
  }
}
 
const heapSort = (nums: number[]) => {
  for (let i = (nums.length >> 1) - 1; i >= 0; i--) ajustHeap(nums, i, nums.length) // 建堆操作（从树的倒数第二层最后一个元素开始）
  for (let i = nums.length - 1; i > 0; i--) {
    swap(nums, 0, i)
    ajustHeap(nums, 0, i) // 以根节点为起点，从顶至底进行堆化
  }
}

前述几种排序算法都属于“基于比较的排序算法”，它们通过比较元素间的大小来实现排序，此类排序算法的时间复杂度无法超越 O(nlogn)。下面几种“非比较排序算法”，它们的时间复杂度可以在理想情况下达到线性阶。

桶排序（Bucket Sort）

它通过设置一些具有大小顺序的桶，每个桶对应一个数据范围，将数据分配到各个桶中；然后在每个桶内部分别执行排序（语言自带的排序方法）；最终按照桶的顺序将所有数据合并。桶排序适用于处理体量很大的数据。桶排序的时间复杂度理论上可以达到 O(n)，关键在于将元素均匀分配到各个桶中，因为实际数据往往不是均匀分布的。

计数排序（Counting Sort）

统计每个元素的出现次数，然后按照统计信息重建排序后的列表。适用于数据量大但数据范围较小的整数数组。

const countingSort = (nums: number[]) => {
  // 找到最大值
  const max = Math.max(...nums)
  // 统计各数字的出现次数
  const counter = new Array<number>(max + 1).fill(0)
  for (const num of nums) counter[num]++
  // 求 counter 的前缀和，将“出现次数”转换为“尾索引”；即 counter[num]-1 是 num 在 ans 中最后一次出现的索引
  for (let i = 0; i < max; i++) counter[i + 1] += counter[i]
  // 倒序遍历 nums ，将各元素填入结果数组 ans。倒序遍历 nums 可以避免改变相等元素之间的相对位置，从而实现稳定排序。
  const ans = new Array<number>(nums.length)
  for (let i = nums.length - 1; i >= 0; i--) {
    const num = nums[i]
    ans[--counter[num]] = num
  }
  // 使用结果数组 ans 覆盖原数组 nums
  for (let i = 0; i < nums.length; i++) nums[i] = ans[i]
}

基数排序（Radix Sort）

核心思想与计数排序一致，也通过统计个数来实现排序。在此基础上，基数排序利用数字各位之间的递进关系，依次对每一位进行排序，从而得到最终的排序结果。适用于数值范围较大的情况，但前提是数据必须可以表示为固定位数的格式，且位数不能过大。

// 获取元素 num 的第 k 位，其中 exp = 10^(k-1)，传入 exp 而非 k 可以避免在此重复执行昂贵的次方计算
const digit = (num: number, exp: number) => Math.floor(num / exp) % 10
 
// 计数排序（根据 nums 第 k 位排序）
const countingSortDigit = (nums: number[], exp: number) => {
  const counter = new Array(10).fill(0)
  for (let i = 0; i < nums.length; i++) counter[digit(nums[i], exp)]++
  for (let i = 1; i < counter.length; i++) counter[i] += counter[i - 1]
  const ans = new Array<number>(nums.length)
  for (let i = nums.length - 1; i >= 0; i--) {
    const d = digit(nums[i], exp)
    ans[--counter[d]] = nums[i]
  }
  for (let i = 0; i < nums.length; i++) nums[i] = ans[i]
}
 
const radixSort = (nums: number[]) => {
  const max = Math.max(...nums)
  for (let exp = 1; exp <= max; exp *= 10) countingSortDigit(nums, exp)
}