JavaScript的排序算法——堆排序

堆排序（Heap Sort）

堆排序（Heap Sort）是一种基于比较的排序算法。堆排序可以被认为是一种改进版的排序算法，它将输出区域分为排序区域和未排序区域，并通过提取最大元素移动到排序区域来迭代缩小未排序区域。

堆排序（Heap Sort）
堆排序（Heap Sort）

复杂度

算法	最好情况	平均情况	最坏情况	空间复杂度	稳定性
堆排序	O(n log n)	O(n log n)	O(n log n)	O(1)	不稳定

ES6实现

function HeapSort(arr) {
  let heapSize = arr.length;
  buildHeap(arr);
  while(heapSize > 1) { 
    const temp = arr[0];
    arr[0]=arr[heapSize-1];
    arr[heapSize-1] = temp;
    heapSize--;
    if (heapSize>1) {
      heapify(arr, heapSize, 0);
    }
  }
    return arr;
}
function buildHeap(arr) {
  const heapSize = arr.length;
  const firstHeapifyIndex = Math.floor(heapSize/2-1);
  for (let i=firstHeapifyIndex; i >= 0; i--) {
    heapify(arr, heapSize, i);
  }
}
function heapify(arr, heapSize, i) {
  const leftIndex = i * 2 + 1;
  const rightIndex = i * 2 + 2;
  let biggestValueIndex = i;
  if (leftIndex < heapSize && arr[leftIndex] > arr[biggestValueIndex]) {
    biggestValueIndex = leftIndex; 
  }
  if (rightIndex < heapSize && arr[rightIndex] > arr[biggestValueIndex]) {
    biggestValueIndex = rightIndex;
  }
  if (biggestValueIndex !== i) { 
    const temp = arr[i];
    arr[i] = arr[biggestValueIndex];
    arr[biggestValueIndex] = temp;
    heapify(arr, heapSize, biggestValueIndex);
  }
}

参考

• 维基百科
• 百度百科

相关阅读

JavaScript的排序算法——冒泡排序
JavaScript的排序算法——选择排序
JavaScript的排序算法——插入排序
JavaScript的排序算法——归并排序
JavaScript的排序算法——快速排序