>[success] # 使用堆进行排序 ~~~ 1.堆两种形式，一种是最大堆，一种是最小堆，我们可以利用这个特性对数组进行快速排序 ，这样排序的时间复杂度'O(nlogn)' 2.用堆进行排序当然需要两步，第一步是吧数组中杂乱无章的数据先变成'堆'，这个过程时间复杂度 为'O(n)',当整个'堆'建立完成后，需要对其排序，树排序是根据树的高度，堆的好处就是因为定义概念 将整体高度和数组长度相比是更短所用的时间也是更少的'O(nlogn)',因此这个建堆和排序过程我们可以 看做成'O(nlogn)' 3.用最大堆得到一个升序排列的数组（从最小到最大）。要这个数组按降序排列，可以用最小堆代替。 ~~~ >[info] ## 代码实现 ~~~ const Compare = { LESS_THAN: -1, BIGGER_THAN: 1, EQUALS: 0 }; function defaultCompare(a, b) { if (a === b) { return Compare.EQUALS; } return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN; } function reverseCompare(compareFn) { return (a, b) => compareFn(b, a); } function swap(array, a, b) { /* const temp = array[a]; array[a] = array[b]; array[b] = temp; */ [array[a], array[b]] = [array[b], array[a]]; } // 将数组变成堆结构，这是一个创建堆的过程 function heapify(array, index, heapSize, compareFn) { let largest = index; const left = (2 * index) + 1; const right = (2 * index) + 2; if (left < heapSize && compareFn(array[left], array[index]) > 0) { largest = left; } if (right < heapSize && compareFn(array[right], array[largest]) > 0) { largest = right; } if (largest !== index) { swap(array, index, largest); heapify(array, largest, heapSize, compareFn); } } // 创建调用的方法 function buildMaxHeap(array, compareFn) { for (let i = Math.floor(array.length / 2); i >= 0; i -= 1) { heapify(array, i, array.length, compareFn); } return array; } // 将堆进行排序 function heapSort(array, compareFn = defaultCompare) { let heapSize = array.length; // 用数组创建一个最大堆用作源数据。 buildMaxHeap(array, compareFn); while (heapSize > 1) { // 在创建最大堆后，最大的值会被存储在堆的第一个位置。我们要将它替换为堆的最后一个 // 值，将堆的大小减 1。 swap(array, 0, --heapSize); // 们将堆的根节点下移并重复步骤 2 直到堆的大小为 1 heapify(array, 0, heapSize, compareFn); } return array; } ~~~