學號：20021211189? ? ? ?姓名：趙治偉
【嵌牛導讀】堆排序（Heapsort）是利用二叉堆的概念來排序的選擇排序算法卖宠，分為兩種：
升序排序：利用最大堆進行排序
降序排序：利用最小堆進行排序
【嵌牛鼻子】堆排序算法
【嵌牛正文】
給定一個最大堆如下圖所示，以該最大堆進行演示堆排序
首先筷畦，刪除堆頂元素10（即最大的元素）刺洒，并將最后的元素3補充到堆頂，刪除的元素10逆航，放置于原來最后的元素3的位置
根據二叉堆的自我調整，第二大的元素9會成為二叉堆新的堆頂
刪除元素9拇惋，元素8成為最大堆堆頂
刪除元素8女揭，元素7成為最大堆堆頂
依次刪除最大元素，直至所有元素全部刪除
此時磷仰，被刪除的元素組成了一個從小到大排序的序列
// 下沉調整
// 最大堆
function downAdjust(arr, parentIndex, length) {
? ? // 緩存父節(jié)點的值灶平，用于最后進行賦值，而不需要每一步進行交換
? ? let temp = arr[parentIndex];
? ? // 孩子節(jié)點下標逢享，暫時定為左孩子節(jié)點下標
? ? let childIndex = 2 * parentIndex + 1;
? ? while (childIndex < length) {
? ? ? ? // 當存在右孩子節(jié)點，且右孩子節(jié)點的值小于左孩子節(jié)點的值瞒爬，childIndex記錄為右孩子節(jié)點的下標
? ? ? ? // childIndex實際記錄的是最小的孩子節(jié)點的下標
? ? ? ? if (childIndex + 1 < length && arr[childIndex + 1] > arr[childIndex]) {
? ? ? ? ? ? childIndex++;
? ? ? ? }
? ? ? ? // 如果父節(jié)點的值比孩子節(jié)點的值都小，則調整結束
? ? ? ? if (temp >= arr[childIndex]) {
? ? ? ? ? ? break;
? ? ? ? }
? ? ? ? // 將最小的孩子節(jié)點的值賦值給父節(jié)點
? ? ? ? arr[parentIndex] = arr[childIndex];
? ? ? ? parentIndex = childIndex;
? ? ? ? childIndex = 2 * parentIndex + 1;
? ? }
? ? arr[parentIndex] = temp;
}
// 堆排序
function sort(arr) {
? ? // 把無序數(shù)組構建成二叉堆
? ? for (let i = parseInt(arr.length / 2) - 1; i >= 0; i--) {
? ? ? ? downAdjust(arr, i, arr.length);
? ? }
? ? console.log(arr);
? ? // 循環(huán)刪除堆頂元素矢空，移到集合尾部，調節(jié)堆產生新的堆頂
? ? for (let i = arr.length - 1; i > 0; i--) {
? ? ? ? // 最后一個元素與第一個元素交換
? ? ? ? [arr[0], arr[i]] = [arr[i], arr[0]];
? ? ? ? downAdjust(arr, 0, i);
? ? }
}
let arr = [10, 9, 8, 5, 6, 7, 1, 4, 2, 3];
sort(arr);
console.log(arr);
下沉調整的時間復雜度等同于堆的高度O(logn)屁药，構建二叉堆執(zhí)行下沉調整次數(shù)是n/2柏锄，循環(huán)刪除進行下沉調整次數(shù)是n-1，時間復雜度約為O(nlogn)
堆排序算法排序過程中需要一個臨時變量進行兩兩交換趾娃，所需要的額外空間為1，因此空間復雜度為O(1)
堆排序算法在排序過程中茫舶，相同元素的前后順序有可能發(fā)生改變，所以堆排序是一種不穩(wěn)定排序算法
