沐码小站

本文介绍一下快速排序、归并排序、冒泡排序的JS实现。

一、快速排序

思想：分治法

1. 选定基数，将数组按照大小归到基数左右两边；
2. 对第一步基数两边的子数组，递归执行第一步

function quickSort(list, left = 0, right = list.length - 1) {
  if (left >= right) return
  let lIdx = left, rIdx = right, mid = list[right]
  list.slice(left, right + 1).forEach(item => item > mid ? list[rIdx--] = item : list[lIdx++] = item)
  quickSort(list, left, rIdx - 1)
  quickSort(list, rIdx + 1, right)
}

二、归并排序

思想：（分治法）将两个有序数组合并成一个大的有序数组，只需要不断地将两个列表中的排头元素中较小（升序，降序则是较大）的一个取出放到新数组，不断重复此过程直到两个原数组中的数都被取完。对于每一个数组，首先划分为长度为1的数组(天然有序)，然后两两合并为有序数组，不断重复，最终整个数组都将有序。

function merge(l1, l2) {
  let i1 = 0, i2 = 0, result = []
  while (i1 < l1.length && i2 < l2.length) result.push(l1[i1] < l2[i2] ? l1[i1++] : l2[i2++])
  let rest = i1 >= l1.length ? l2.slice(i2) : l1.slice(i1)
  return result.concat(rest)
}

function mergeSort(list) {
  if (list.length <= 1) return [...list]
  let mid = Math.floor(list.length / 2)
  return merge(mergeSort(list.slice(0, mid)), mergeSort(list.slice(mid)))
}

三、冒泡排序

特点：原地排序，不消耗额外空间来存储待排序的元素。

function bubbleSort (list) {
  for (let i = 0; i < list.length; i++) {
    for (let j = 1; j < list.length - i; j++) {
      list[j] < list[j - 1] && ([list[j - 1], list[j]] = [list[j], list[j - 1]])
    }
  }
}

四、堆排序

function heapSort (list) {
    for (let i = 1; i < list.length; i++) {
        let idx = i, pIdx = Math.floor(idx / 2)
        while (idx > 0 && list[pIdx] < list[idx]) {
            [list[pIdx], list[idx]] = [list[idx], list[pIdx]]
            idx = pIdx
            pIdx = Math.floor(idx / 2)
        }
    }
    for (let i = list.length - 1; i > 0; i--) {
        [list[0], list[i]] = [list[i], list[0]]
        let pIdx = 0, lIdx = pIdx * 2 + 1
        while (lIdx < i) {
            let sIdx = lIdx, rIdx = lIdx + 1
            if (rIdx < i && list[rIdx] > list[lIdx]) sIdx = rIdx
            if (list[sIdx] < list[pIdx]) break;
            [list[sIdx], list[pIdx]] = [list[pIdx], list[sIdx]]
            pIdx = sIdx
            lIdx = pIdx * 2 + 1
        }
    }
    return list
}