排序算法汇总

• 冒泡排序
• 选择排序
• 插入排序
• 希尔排序
• 归并排序
• 快速排序
• 堆排序

冒泡排序

冒泡排序

核心思路：比较“大”的元素向后冒泡。

时间复杂度：O(n2)

缺点：频繁交换元素，更多的内存读写操作，影响执行效率。

const arr = [2, 3, 12, 4, 2, 52, 23, 42, 10, 231, 13]

const bubbleSort = (arr, compare) => {
  compare = compare || ((a, b) => a < b)
  // 优化1：如果过程中不存在交换的状况，说明已经排序好了
  let isSortCompleted = true
  // 优化2：记录最后一次交换的index
  let lastSwapIndex = arr.length - 1
  // 遍历的边界
  let sortBorder = arr.length - 1
  for (let i = 0;i < arr.length;i++) {
    for (let j = 0;j < sortBorder;j++) {
      if (!compare(arr[j], arr[j + 1])) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
        isSortCompleted = false
        lastSwapIndex = j
      }
    }
    sortBorder = lastSwapIndex
    if (isSortCompleted) break
  }
  return arr
}

console.log(bubbleSort(arr, (a, b) => a < b))
// [2, 2, 3, 4, 10, 12, 13, 23, 42, 52, 231]

选择排序

选择排序

核心思路：依次选择比较“大”的元素，挨个往前面放。

时间复杂度：O(n2)

缺点：不稳定排序，值相同的元素排序后可能顺序发生了变化。

const arr = [2, 3, 12, 4, 2, 52, 23, 42, 10, 231, 13]

const selectSort = (arr, compare) => {
  compare = compare || ((a, b) => a < b)

  for (let i = 0;i < arr.length;i++) {
    for (let j = i + 1;j < arr.length;j++) {
      if (!compare(arr[i], arr[j])) {
        [arr[i], arr[j]] = [arr[j], arr[i]]
      }
    }
  }
  return arr
}

console.log(selectSort(arr, (a, b) => a < b))
// [2, 2, 3, 4, 10, 12, 13, 23, 42, 52, 231]

插入排序

插入排序

核心思路：对比当前元素和前面的元素，如果不符合情况则将前面元素依次后移一位，直到找到正确的位置进行插入。

时间复杂度：最坏情况下O(n2)

const arr = [2, 3, 12, 4, 2, 52, 23, 42, 10, 231, 13]

const insertSort = (arr, compare) => {
  compare = compare || ((a, b) => a < b)

  for (let i = 1;i < arr.length;i++) {
    // 需要插入的元素
    const insertValue = arr[i]
    let j = i - 1
    // 与前面元素进行判断，不满足的话依次将元素后移
    while (j >= 0 && !compare(arr[j], insertValue)) {
      arr[j + 1] = arr[j]
      j--
    }
    arr[j + 1] = insertValue
  }
  return arr
}

console.log(insertSort(arr, (a, b) => a < b))
// [2, 2, 3, 4, 10, 12, 13, 23, 42, 52, 231]

希尔排序

希尔排序

核心思路：相当于在插入排序之前做了一个预处理，让数据变得更加“有序”。这样在插入排序时，就会进行更少的查找和对比了。这里的”预处理“过程是由大间隔的插入排序到小间隔的插入排序的过程。

const arr = [2, 3, 12, 4, 2, 52, 23, 42, 10, 231, 13]

const shellSort = (arr, compare) => {
  compare = compare || ((a, b) => a < b)

  let hill = 0
  // 计算希尔间间隔序列，主要目的是使得计算量尽可能的小
  while (hill < arr.length / 3) {
    hill = hill * 3 + 1
  }

  while (hill >= 1) {
    for (let i = hill;i < arr.length;i++) {
      // 需要插入的元素
      const insertValue = arr[i]
      // 与前面元素进行判断，不满足的话依次将元素后移
      let j = i - hill
      for (;j >= 0 && !compare(arr[j], insertValue);j = j - hill) {
        arr[j + hill] = arr[j]
      }
      arr[j + hill] = insertValue
    }

    hill = (hill - 1) / 3
  }


  return arr
}

console.log(shellSort(arr, (a, b) => a < b))
// [2, 2, 3, 4, 10, 12, 13, 23, 42, 52, 231]

归并排序

归并排序

核心思想：将数组递归平分，先将最小的数组排序，然后将这些数组进行合并。由于小数组已经存在顺序了，所以合并的时候只需要遍历一遍即可。

时间复杂度：递归过程为logn，每一层的排序为n，因此复杂度为O(nlogn)

const arr = [2, 3, 12, 4, 2, 52, 23, 42, 10, 231, 13]

const merge = (arr, start, end, compare) => {
  // 如果只有一个元素，返回
  if (end === start) return
  // 如果只有两个元素，进行交换
  if (end - start === 1) {
    if (!compare(arr[start], arr[end])) {
      [arr[start], arr[end]] = [arr[end], arr[start]]
    }
    return
  }
  const middle = Math.floor((end + start) / 2)
  merge(arr, start, middle, compare)
  merge(arr, middle + 1, end, compare)

  let leftIndex = 0
  let rightIndex = 0
  let tempArray = []
  // 遍历这一整段数组
  for (let i = start;i <= end;i++) {
    // 左侧数组的值
    const leftValue = arr[start + leftIndex]
    // 右侧数组的值
    const rightValue = arr[middle + 1 + rightIndex]
    if (leftIndex <= middle - start && compare(leftValue, rightValue)) {
      tempArray.push(leftValue)
      leftIndex += 1
    } else {
      tempArray.push(rightValue)
      rightIndex += 1
    }
  }
  // 更改数组的原始顺序
  for (let i = 0;i < tempArray.length;i++) {
    arr[start + i] = tempArray[i]
  }
}

const mergeSort = (arr, compare) => {
  compare = compare || ((a, b) => a < b)
  merge(arr, 0, arr.length - 1, compare)
  return arr
}

console.log(mergeSort(arr, (a, b) => a < b))
// [2, 2, 3, 4, 10, 12, 13, 23, 42, 52, 231]

快速排序

快速排序

核心思路：选取基准值，遍历数组，小于基准值的放入左侧，大于基准值的放入右侧，递归执行，直到最小的数组均完成排序。

时间复杂度：最坏情况下O(n2)，最好情况下O(nlogn)

const arr = [2, 3, 12, 4, 2, 52, 23, 42, 10, 231, 13]

const quickSort = (arr, compare) => {
  if (arr.length <= 1) return arr
  let lesser = []
  let greater = []
  let pivot = arr[0]
  for (let i = 1;i < arr.length;i++) {
    if (compare(arr[i], pivot)) {
      lesser.push(arr[i])
    } else {
      greater.push(arr[i])
    }
  }
  const sortLesser = quickSort(lesser, compare)
  const sortGreater = quickSort(greater, compare)
  return sortLesser.concat(pivot, sortGreater)
}

console.log(quickSort(arr, (a, b) => a < b))
// [2, 2, 3, 4, 10, 12, 13, 23, 42, 52, 231]

堆排序

堆排序

核心思路：先将无序数组构建成堆，然后遍历取堆的头部数据放到数组末尾。

时间复杂度：O(nlogn)

const arr = [2, 3, 12, 4, 2, 52, 23, 42, 10, 231, 13]

const heapDown = (arr, parentIndex, length, compare) => {
  let leftChildIndex = 2 * parentIndex + 1
  let rightChildIndex = 2 * parentIndex + 2

  if (leftChildIndex >= length) {
    // 左index超出界限
    return
  }
  // 找出左右节点的最大值
  // 注意这里的 compare是取反的，因为后续排序时，最大值放到最后面了
  let maxValueIndex = leftChildIndex
  if (rightChildIndex < length && compare(arr[maxValueIndex], arr[rightChildIndex])) {
    maxValueIndex = rightChildIndex
  }

  // 如果 parentValue 符合要求，则跳过。
  if (compare(arr[parentIndex], arr[maxValueIndex])) {
    // 交换位置，然后继续向下调整
    [arr[parentIndex], arr[maxValueIndex]] = [arr[maxValueIndex], arr[parentIndex]]
    heapDown(arr, maxValueIndex, length, compare)
  }
}

const heapSort = (arr, compare) => {
  const middleIndex = Math.floor(arr.length / 2 - 1)
  // 从 n/2-1 长度开始遍历，依次将父元素下层。
  for (let i = middleIndex;i >= 0;i--) {
    heapDown(arr, i, arr.length, compare)
  }

  // 遍历 arr，取出头部数据
  for (let i = arr.length - 1;i >= 0;i--) {
    // 每次都取第一个，然后与最后一个元素交换
    [arr[0], arr[i]] = [arr[i], arr[0]]
    // 交换完后进行调整
    heapDown(arr, 0, i, compare)
  }

  return arr
}

console.log(heapSort(arr, (a, b) => a < b))
// [2, 2, 3, 4, 10, 12, 13, 23, 42, 52, 231]