堆排序 (Heap sort) 就是利用堆(假设利用大顶堆)进行排序的方法 。基本思想是
function HeapSort(arr) { arr = [0, ...arr]; // 方便左右子树表示 //第一步,构建初始堆 for (let i = ~~Math.length / 2; i > 0; i--) { buildHeap(arr, i, arr.length); } for (let i = arr.length; i > 1; i--) { // 交换 [arr[1], arr[i - 1]] = [arr[i - 1], arr[1]]; // 根元素与末尾元素交换,再构建大顶堆 buildHeap(arr, 1, i - 1); } return arr.slice(1); // 移除添加的0元素 } // 构造大顶堆 function buildHeap(arr, i, length) { let temp = arr[i]; for (let j = 2 * i; j <= length; j *= 2) { if (arr[j] < arr[j + 1]) j++; if (temp > arr[j]) break; arr[i] = arr[j]; i = j; } arr[i] = temp; } // ------- 测试 let arr = [3, 9, 5, 2, 6]; console.log(HeapSort(arr)); // [ 9, 5, 6, 2, 3 ] arr = [5, 3, 9, 8, 3, 4]; console.log(HeapSort(arr)); // [ 8, 3, 3, 5, 9, 4 ]