SkyBlog

排序

经典排序算法

这篇文章发布于 2024年01月02日,星期二,06:29,归类于 算法阅读 ? 次,0 条评论

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

// 使用到的原地交换方法
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)
}