堆排序

[louzhedong]

算法名称

堆排序

实现思路

• 基于完全二叉树
• 每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆
• 创建一个最大堆
• 将根（最大值）与堆尾交换
• 把堆的尺寸缩小1，即不需要最后一项，将剩余的堆调整为最大堆
• 重复交换，调整，最后得到一个升序的数组

算法分析

时间复杂度是O(N*logN)

算法实现

/**
 * 堆排序
 * @param {} array 
 */
function HeapSort(array) {
  var length = array.length;
  buildMaxHeap(array);
  for (var i = length - 1; i > 0; i--) {
    swap(array, 0, i);
    length--;
    heapify(array, 0, length);
  }
}

function swap(array, i, j) {
  var temp = array[i];
  array[i] = array[j];
  array[j] = temp;
}

function buildMaxHeap(array) {
  var length = array.length;
  for (var i = length - 1; i >= 0; i--) {
    heapify(array, i, array.length);
  }
}

function heapify(array, i, length) {
  var left = i * 2 + 1,
    right = i * 2 + 2;
  largestIndex = i

  if (left < length && array[left] > array[largestIndex]) {
    largestIndex = left;
  }

  if (right < length && array[right] > array[largestIndex]) {
    largestIndex = right;
  }

  if (largestIndex !== i) {
    swap(array, largestIndex, i);
    heapify(array, largestIndex, length);
  }

}