任先生的笔记库

# 排序算法

  在计算机科学中，排序算法非常重要，且可能非常耗时，前人已经研究了一套成熟的方案来实现排序，我们只需要站在巨人的肩膀上学习即可。

  通常情况下，我们可以使用以下标准对排序算法进行评价：

  • 时间复杂度：使用大 O 表示法，也可以测试消耗的时间
  • 内存使用量：比如外部排序，使用磁盘来存储排序的数据
  • 稳定性：稳定的排序算法会让原本有相等键值的记录维持相对次序
  • 排序方法：插入、交互、选择、合并等等

维基百科：排序算法 (opens new window)

提示

  如下的测试数组为：[3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]

  排序算法可视化：https://www.chrislaux.com (opens new window) 、sort-visualizer (opens new window)

  博客园文章参考：十大经典排序算法（动图演示） (opens new window)

# 一、基础排序算法

# 1、冒泡排序

  每经过一轮，就可以将当前轮中的最大值放置在最后。

图示：

  • Bubble Sort

代码实现：

优化版本 
export function bubbleSort_Pro(arr: number[]): number[] {
  const n = arr.length

  // 经历n-1轮
  for (let i = 0; i < n - 1; i++) {
    let isSwapped = false

    for (let j = 0; j < n; j++) {
      // 是否交换
      if (arr[j] > arr[j + 1]) {
        ;[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]

        isSwapped = true // 发生了交换
      }
    }

    // 是否启动下一轮
    if (!isSwapped) break
  }

  return arr
}

export function bubbleSort(arr: number[]): number[] {
  const length = arr.length

  // 经历n-1轮
  for (let i = 0; i < length - 1; i++) {
    // 当前轮中
    for (let j = 0; j < length - 1 - i; j++) {
      const num1 = arr[j]
      const num2 = arr[j + 1]
      // 是否交换
      if (num1 > num2) {
        const temp = arr[j]
        arr[j] = arr[j + 1]
        arr[j + 1] = temp
      }
    }
  }

  return arr
}

# 2、选择排序

  每一轮中，只需要找出最小值并进行一次交换。

图示：

  • Selection Sort

代码实现：

优化版本 
export function selectionSort_Pro(arr: number[]): number[] {
  const n = arr.length

  // 经历n-1轮
  for (let i = 0; i < n - 1; i++) {
    let minIndex = i // 设置默认值

    // 更新最小值索引
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j
      }
    }

    // 数据交换
    if (i !== minIndex) {
      ;[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
    }
  }

  return arr
}

export function selectionSort(arr: number[]): number[] {
  const length = arr.length

  // 经历n-1轮
  for (let i = 0; i < length - 1; i++) {
    let minIndex = i // 设置默认值

    // 更新最小值索引
    for (let j = i + 1; j < length; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j
      }
    }

    // 数据交换
    const temp = arr[i]
    arr[i] = arr[minIndex]
    arr[minIndex] = temp
  }

  return arr
}

# 3、插入排序

  每一轮依次从后面抽出一个元素，并向前推进（插入），直到找到合适的位置。

类似于 打牌时的理牌过程

图示：

  • Insertion Sort

代码实现：

export function insertSort(arr: number[]): number[] {
  const n = arr.length

  // 经历n-1轮
  for (let i = 0; i < n - 1; i++) {
    // 暂存抽离的元素
    const pumpElement = arr[i + 1]

    // 获取pumpElement插入的位置
    let endIndex = i
    while (arr[endIndex] > pumpElement && endIndex >= 0) {
      arr[endIndex + 1] = arr[endIndex] // 后移
      endIndex--
    }

    // 插入pumpElement
    arr[endIndex + 1] = pumpElement
  }

  return arr
}

# 优缺点分析

  • 冒泡排序：最坏时它的时间复杂度为 O(n^2)，对于大量数据的排序会非常慢
  • 选择排序：最坏时它的时间复杂度为 O(n^2)，但数据交换次数较少
  • 插入排序：最坏时它的时间复杂度为 O(n^2)，在某些场景下表现良好

# 二、重点排序算法

# 1、归并排序 🎈

  将待排序数组分成若干子数组，然后相邻的子数组归并为一个有序数组，最后将这些有序数组归并成一个整体有序的数组。

这个算法在很多流行的框架、引擎等有广泛的应用，是由“现代计算机之父” 约翰-冯诺依曼于 1945 年首次提出的一个排序算法。

其核心就是我们常说的“分治法”，并且算法复杂度为 O(nlogn)，是一个比较高效的排序算法

图示：

  • Merge Sort

步骤分解：

参考：Merge Sort Algorithm (opens new window)

  • 分解（Divide）
  • 合并（Merge）
在线测试

代码实现：

export function mergeSort(arr: number[]): number[] {
  // 递归结束条件：分解成单个元素为止
  if (arr.length <= 1) return arr

  // 1、分解
  const midIndex = Math.floor(arr.length / 2)

  // - 递归执行
  const leftArr = mergeSort(arr.slice(0, midIndex))
  const rightArr = mergeSort(arr.slice(midIndex))

  // ==========
  // ==========

  // 2、合并
  const newArr: number[] = []

  let leftIndex = 0
  let rightIndex = 0

  // -- 左右数组有序合并
  while (leftIndex < leftArr.length && rightIndex < rightArr.length) {
    if (leftArr[leftIndex] <= rightArr[rightIndex]) {
      newArr.push(leftArr[leftIndex])
      leftIndex++
    } else {
      newArr.push(rightArr[rightIndex])
      rightIndex++
    }
  }

  // -- 剩余元素处理（本身有序，放入即可）
  if (leftIndex < leftArr.length) {
    newArr.push(...leftArr.slice(leftIndex))
  }
  if (rightIndex < rightArr.length) {
    newArr.push(...rightArr.slice(rightIndex))
  }

  return newArr
}

# 2、快速排序 🎈

  将一个大数组根据基准元素（pivot）值大小分为两个小数组，并通过递归对两个小数组进行排序。

  快速排序 也称 划分交换排序（partition-exchange sort）可以说是现今综合表现最好的排序算法之一，是由计算机科学家 Tony Hoare（东尼-霍尔）于 1960 年初期发明的一个排序算法，其实现快速排序的思想非常巧妙，在计算机科学中有广泛的应用。

  它的核心同样采用“分治法”，不同的是它不需要额外的数组空间（newArr），而是在原地进行排序。在最好的情况下其时间复杂度为 O(nlogn)，但最坏的情况时时间复杂度却是 O(n^2)，为了避免这种情况我们可以堆 pivot 采用三数取中法等解决

图示：

  • Quick Sort

网络上也有不少教程中基准元素 pivot 采用的是头元素（即）

pivot 初始值为 首元素（不喜欢）
  • 可视化 1：

https://www.chrislaux.com/quicksort

  • 可视化 2：

黄色的柱子 即 pivot

步骤分解：

参考：🎈Sorting Algorithms (Quick Sort, Merge Sort) (opens new window)

  • 左侧找大于 pivot 的元素停下，等待与右侧侧找小于 pivot 的元素 互换

  • 右侧找小于 pivot 的元素停下，等待与左侧侧找大于 pivot 的元素 互换

  • 当右侧指针 大于 左侧指针时，停止循环

代码实现：

export function quickSort(arr: number[]): number[] {
  //

  // 编写递归划分函数
  function partition(leftIndex: number, rightIndex: number) {
    // 递归结束条件：数组长度小于等于0
    if (leftIndex >= rightIndex) return

    // 1、定义 pivot (选择最后一个元素)
    const pivot = arr[rightIndex]

    // 2、定义双指针 i、j
    let i = leftIndex
    let j = rightIndex - 1

    // 3、划分数组
    while (i <= j) {
      // 左侧找大于 pivot 的元素停下
      while (arr[i] < pivot) {
        i++
      }

      // 右侧找小于 pivot 的元素停下
      while (arr[j] > pivot) {
        j--
      }

      // 数据交换（为上述while循环找到的两个元素添加限制条件）
      if (i <= j) {
        const temp = arr[i]
        arr[i] = arr[j]
        arr[j] = temp

        i++
        j--
      }
    }

    // 4、Pivot 居中
    const temp = arr[i]
    arr[i] = arr[rightIndex]
    arr[rightIndex] = temp

    // 继续递归划分
    partition(leftIndex, j) // 左侧数组
    partition(i + 1, rightIndex) // 右侧数组
  }

  // 执行划分
  partition(0, arr.length - 1)

  return arr
}

# 3、堆排序 ✨

  每一轮中，通过堆结构找出最大值并进行一次交换。

不同的是，堆可以将获取最大值的效率从 O(n*n) 提升到 O(n*logn)

需要注意的是，堆排序是不稳定的，相同元素的相对位置可能会发生变化

提示

  堆排序 算是 选择排序 的一种优化手段（同样是每一轮找最值）

图示：

代码实现：

heapify_down 
// 注意：这里的下滤操作中，arr是动态变化的
export function heapify_down(start: number, data: number[], length: number) {
  let elementIndex = start

  // 没有左子节点结束
  while (2 * elementIndex + 1 <= length - 1) {
    let leftChildIndex = 2 * elementIndex + 1
    let rightChildIndex = leftChildIndex + 1

    // 待交换目标index（左右子树的较大者）
    let largerIndex = leftChildIndex
    if (rightChildIndex < length && data[rightChildIndex] >= data[leftChildIndex]) {
      largerIndex = rightChildIndex
    }

    // 判断是否 中途到底
    if (data[elementIndex] >= data[largerIndex]) break

    // 交换位置
    const temp = data[elementIndex]
    data[elementIndex] = data[largerIndex]
    data[largerIndex] = temp

    elementIndex = largerIndex // 记录值更新
  }
}

import { heapify_down } from './utils/buildMaxHeap'

export function heapSort(arr: number[]): number[] {
  //
  // 1、初始化 最大堆
  const n = arr.length
  const start = Math.floor((n - 1) / 2) // 最底部的第一个非叶子节点

  for (let i = start; i >= 0; i--) {
    heapify_down(i, arr, n)
  }

  // 2、最大值 收集
  for (let i = n - 1; i > 0; i--) {
    // 最大值 交换至 尾部
    const temp = arr[0]
    arr[0] = arr[i]
    arr[i] = temp

    // root元素 下滤
    heapify_down(0, arr, i)
  }

  return arr
}

# 4、希尔排序

提示

  希尔排序 算是 插入排序 的一种优化手段

希尔排序由 Donald Shell（唐纳森-希尔）于 1959 年发明，第一个突破 O(n2)的排序算法，是简单插入排序的改进版

它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序

图示：

可视化：https://www.chrislaux.com/shellsort

代码实现：

export function shellSort(arr: number[]): number[] {
  const n = arr.length

  // 设置不同的增量（步长/间隔）
  let gap = Math.floor(n / 2)
  let endGapIndex = Math.floor(n / gap) * gap

  // 不断改变步长
  while (gap > 0) {
    // 当前步长组成的 gap 数列集合
    for (let i = gap; i < n; i++) {
      let j = i
      const temp = arr[i]

      // 当前轮 gap 数列 插入排序
      while (j >= gap - 1 && temp < arr[j - gap]) {
        arr[j] = arr[j - gap]

        j = j - gap
      }

      arr[j] = temp
    }

    // 继续缩小gap
    gap = Math.floor(gap / 2)
  }

  return arr
}

# 三、其他排序算法

# 1、计数排序

图示：

代码实现：

# 2、基数排序

图示：

代码实现：

# 3、桶排序

更新于 : 8/7/2024, 2:16:31 PM

← 动态规划 →

Apache License 2.0 | Copyright © 2022 lencamo All Rights Reserved | 蜀ICP备2022012538号-2