/**
? ? * 堆排序 時間復(fù)雜度O(nlogn)
? ? * 初始化建堆O(n) 排序重建堆O(nlogn)
? ? *
? ? * @param {any} arr
? ? * @returns
? ? *
? ? * @memberof sort
? ? */
? ? sort7(arr){
? ? var len = arr.length;
? ? var tem;
? ? this.buildMaxHeap(arr);
? ? for(var i = len - 1; i > 0; i --){
? ? tem = arr[i];
? ? arr[i] = arr[0];
? ? arr[0] = tem;
? ? this.maxHeap(arr, 0 , --len);
? ? }
? ? return arr;
? ? }
? ? /**
? ? * 建立最大堆
? ? *
? ? * @param {any} arr
? ? *
? ? * @memberof sort
? ? */
? ? buildMaxHeap(arr){
? ? var lastFather = Math.floor(arr.length / 2) - 1;//堆的最后一個父節(jié)點
? ? for(var i = lastFather; i > 0; i --){
? ? this.maxHeap(arr, i, arr.length);
? ? }
? ? }
? ? /**
? ? * 對重建堆排序
? ? *
? ? * @param {any} arr
? ? * @param {any} index
? ? * @param {any} heapSize
? ? *
? ? * @memberof sort
? ? */
? ? maxHeap(arr, index, heapSize){
? ? var tem = index; //記錄入?yún)⒃叵聵?biāo)
? ? var leftChildIndex = 2 *index + 1; //元素的左子樹的元素下標(biāo)
? ? var rightChildeIndex = 2 * index + 2;//元素的右子樹的元素下標(biāo)
? ? if( leftChildIndex < heapSize && arr[leftChildIndex] > arr[index]){
? ? index = leftChildIndex;
? ? }
? ? if( rightChildeIndex < heapSize && arr[rightChildeIndex] > arr[index]){
? ? index = rightChildeIndex;
? ? }
? ? if(index != tem){
? ? var t = arr[tem];
? ? arr[tem] = arr[index];
? ? arr[index] = t;
? ? this.maxHeap(arr, index, heapSize);
? ? }
? ? }
