升序排列数组

  1. function heapify(arr, idx, len) {
  2.   let maxPoint = idx;
  3.   const left = idx * 2 + 1;
  4.   const right = idx * 2 + 2;
  6.   if (left < len && arr[left] > arr[maxPoint]) {
  7.     maxPoint = left;
  8.   }
  9.   if (right < len && arr[right] > arr[maxPoint]) {
  10.     maxPoint = right;
  11.   }
  13.   if (maxPoint !== idx) {
  14.     [arr[idx], arr[maxPoint]] = [arr[maxPoint], arr[idx]];
  15.     heapify(arr, maxPoint, len);
  16.   }
  17. }
  19. function heapSort(arr) {
  20.   let len = arr.length;
  22.   for (let i = Math.floor(len / 2) - 1; i >= 0; i--) {
  23.     heapify(arr, i, len);
  24.   }
  26.   while (--len) {
  27.     [arr[0], arr[len]] = [arr[len], arr[0]];
  28.     heapify(arr, 0, len);
  29.   }
  31.   return arr;
  32. }

算法测试

  1. console.log(heapSort([6, 2, 1, 8, 7, 5]));
  2. // [ 1, 3, 5, 6, 8, 9 ]
  4. console.log(heapSort([4, 7, 2, 5, 3, 1, 9, 0]));
  5. // [ 0, 1, 2, 3, 4, 5, 7, 9 ]
  7. console.log(heapSort([12, 0, 3, 4, 3, 8]));
  8. // [ 0, 3, 3, 4, 8, 12 ]