10. 排序

冒泡排序

• 原理：连续地比较相邻元素，如果它们的顺序错误就交换它们，每一轮循环都确定好一个最大的数，剩下的数继续如此（就像把一个大数慢慢冒泡上去一样）
• 时间复杂度：O(n^2)
• 空间复杂度：O(1)
• 稳定性：稳定（在冒泡中遇到相等元素不交换）

function bubbleSort(arr) {
  const len = arr.length
  
  for (let i = 0; i < len - 1; i++) { // 每次循环确定一个最大数放到最右边，一共需要循环 len - 1 次（如3个数就需要循环2次）。i：表示已经排好了几个数
    let flag = false // 优化：标记本轮是否发生交换
    
    for (let j = 0; j < len - 1 - i; j++) { // 没有确定位置的数两两进行比较。j：表示每轮循环中当前在比较哪个位置的数
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]] // j > j + 1，则 j 右移
        flag = true
      }
    }
    
    if (!flag) break // 无交换说明已有序，提前终止
  }
}

快速排序

• 原理：一种基于分治策略的排序算法，把一个序列按照基准数分为较小和较大的两个子序列，然后递归地排序两个子序列
• 步骤：
  • 选取数组最左端元素作为基准数，初始化两个指针 i 和 j 分别指向数组的两端
  • 设置一个循环，在每轮中使用 i（j）分别寻找第一个比基准数大（小）的元素，然后交换这两个元素
  • 循环执行步骤 2. ，直到 i 和 j 相遇时停止，最后将基准数交换至两个子数组的分界线（i 或 j）
• 时间复杂度：O(nlogn)
• 空间复杂度：O(logn)
• 稳定性：不稳定（基准元素可能被交换到相同元素的另一侧）

function sort(arr) {
  quickSort(arr, 0, arr.length - 1)
}
 
function quickSort(arr, left, right) {
  if (left >= right) return // 子数组长度为 1 时说明子数组排序完成，终止递归
  
  const pivot = partition(arr, left, right) // 找到划分后 pivot 的位置，然后递归排序它的左右两部分
  quickSort(arr, left, pivot - 1)
  quickSort(arr, pivot + 1, right)
}
 
// 排序函数，对数组排序，并返回排序后 pivot 的位置
function partition(arr, left, right) {
  const pivot = arr[left] // 以最左边 left 位置的数为基准数
  let i = left + 1, j = right // pivot 后面的数参与比较
  
  // 把<=pivot的数全部放在左边，>=pivot的数全部放在右边
  while (i <= j) {
    while (i <= j && arr[i] <= pivot) i++
    while (i <= j && arr[j] >= pivot) j--
    if (i < j) {
      [arr[i], arr[j]] = [arr[j], arr[i]]
    }
  }
  
  [arr[left], arr[j]] = [arr[j], arr[left]] // 循环结束时 j 指向最后一个小于等于 pivot 的元素，所以把它和最左边的数字（也就是 pivot）进行交换
  
  return j // 交换后返回 pivot 的位置
}

选择排序

• 原理：每轮从未排序区间选择最小的元素，将其放到已排序区间的末尾
• 时间复杂度：O(n^2)
• 空间复杂度：O(1)
• 稳定性：不稳定（交换最小数时可能改变相同数的相对位置）

function selectionSort(arr) {
  const len = arr.length
  
  for (let i = 0; i < len - 1; i++) { // 外层循环 i：当前循环轮次要排好第 i 个位置的数
    let minIdx = i // 后面未排序的数中最小值的索引
    for (let j = i; j < len; j++) {
      if (arr[j] < arr[minIdx]) minIdx = j // 记录最小数的索引
    }
    [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]] // 最小数就是要排在第 i 个位置的数
  }
}

插入排序

• 原理：每次选择未排序的一个数，在前面已经排好序的数组中找到它的位置进行插入（类似手动整理一副牌的过程）
• 时间复杂度：O(n^2)
• 空间复杂度：O(1)
• 稳定性：稳定（插入操作过程中，会将元素插入到相等元素的右侧，不会改变它们的顺序）

function insertionSort(arr) {
  const len = arr.length
  
  for (let i = 1; i < len; i++) { // 外层循环 i：当前位置的数需要插入到前面排好的数中
    const cur = arr[i]
    let j = i - 1
    while (j >= 0 && arr[j] > cur) { // 依次往前进行比较，直到找到一个小于等于该数的数
      arr[j + 1] = arr[j]
      j--
    }
    arr[j + 1] = cur // 将该数插入到它应当的位置
  } 
}

归并排序

• 原理：一种基于分治策略的排序算法，通过递归不断地将数组从中点处分开，将长数组的排序问题转换为短数组的排序问题
• 步骤：
  • 划分阶段：递归地把当前数组从中点分割成两半
  • 合并阶段：当子数组长度为 1 时终止划分，开始合并，持续地将左右两个较短的有序数组合并为一个较长的有序数组
• 时间复杂度：O(nlogn)
• 空间复杂度：O(n)
• 稳定性：稳定

function mergeSort(arr) {
  const len = arr.length
  if (len <= 1) return arr // 当子数组长度为 1 时终止递归（单个元素肯定是有序的）
  
  let mid = Math.floor(len / 2)
  let left = arr.slice(0, mid)
  let right = arr.slice(mid)
  return merge(mergeSort(left), mergeSort(right))
}
 
// 将两个有序数组合并成一个有序数组
function merge(left, right) {
  let res = []
  
  let i = 0, j = 0, k = 0 // i：指向left数组，j：指向right数组，k：指向合并后的新数组
  while (i < left.length && j < right.length) { // 依次取两个数组中的较小值放入结果数组
    if (left[i] <= right[j]) {
      res[k] = left[i]
      i++
    } else {
      res[k] = right[j]
      j++
    }
    k++
  }
  
  // left 数组中还有剩余，直接复制到结果数组
  while (i < left.length) {
    res[k++] = left[i++]
  }
  // right 数组中还有剩余，直接复制到结果数组  
  while (j < right.length) {
    res[k++] = right[j++]
  }
  
  return res
}

参考

十大经典排序算法总结 | JavaGuide
第 11 章   排序 - Hello 算法