堆排序

[myLightLin]

简介

你有很多卡片，你的目标是将一堆乱序的数字卡片按顺序排列。堆排序的过程就是，首先构建一个“山”，山顶是最大的卡片，其他卡片按大小逐渐向下排列。然后把山顶的卡片拿到手里，放到一边的“已排序”区域。接着重新调整山的形状，使新的山顶仍是剩下卡片中最大的，重复这个过程，直到所有的卡片都在“已排序”区域，且按照顺序排列。

代码

function heapSort(arr) {
  let n = arr.length
  // 建堆
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
	  heapify(arr, n, i)
  }
  // 排序
  for (let i = n - 1; i > 0; i--) {
    const temp = arr[0]
    arr[0] = arr[i]
    arr[i] = temp
    
    heapify(arr, i, 0)
  }
}

function heapify(arr, n, i) {
  let largest = i
  let left = 2 * i + 1
  let right = 2 * i + 2
  
  if (left < n && arr[left] > arr[largest]) {
    largest = left
  }
  
  if (right < n && arr[right] > arr[largest]) {
    largest = right
  }
  
  if (largest !== i) {
    const swap = arr[i]
    arr[i] = arr[largest]
    arr[largest] = swap
    
    heapify(arr, n, largest)
  }
}

const arr = [12, 11, 13, 5, 6, 7]
heapSort(arr) // [5, 6, 7, 11, 12, 13]

动画演示

总结

1. 时间复杂度：平均时间复杂度和最坏时间复杂度都为 O(n log n)，这是因为建堆过程是 O(n)，而后续的下滤过程是 O(n log n)，所以总的时间复杂度是 O(n log n)。
2. 空间复杂度： O(1)，是原地排序算法。由于在排序的过程总，相等的元素可能会交换其原有的顺序，因此是不稳定的排序算法。
3. 应用场景：堆排序适合数据量大，对内存使用有限制的场景。此外，优先队列也是堆排序的使用场景。