堆排序

• 时间复杂度： O(nlogN)
• 空间复杂度： O(n)

首先，实现一个堆

class Heap {
    constructor() {
        this.data = [null];
    }

    getData() {
        console.log(this.data);
        return this.data;
    }

    insert(num) {
        this.data.push(num);

        this.shiftUp(this.data.length - 1);
    }

    extracMax() {
        if (this.data.length > 1) {
            // var resultArr = this.data.splice(1, 1);
            // debugger;
            swap(this.data, 1, this.data.length - 1);
            var result = this.data.pop();
            this.shiftDown(1);
            return result;
        }
    }

    shiftUp(currentIndex) {
        while (currentIndex > 1 && this.data[currentIndex] > this.data[parseInt(currentIndex / 2)]) {
            swap(this.data, currentIndex, parseInt(currentIndex / 2));
            currentIndex = parseInt(currentIndex / 2);
        }
    }

    shiftDown(currentIndex) {
        // debugger;
        while (this.data[currentIndex * 2] > this.data[currentIndex] || this.data[currentIndex * 2 + 1] > this.data[currentIndex]) {
            if (this.data[currentIndex * 2] < this.data[currentIndex * 2 + 1]) {
                swap(this.data, currentIndex * 2 + 1, currentIndex);
                currentIndex = currentIndex * 2 + 1;
            } else {
                swap(this.data, currentIndex * 2, currentIndex);
                currentIndex = currentIndex * 2;
            }
        }
    }
};

接下来进行排序

var initArr = [9, 8, 7, 6, 5, 4, 3, 2, 1];  // 测试数据

function heapSort() {
    var heapData = new Heap();
    var resultArr = [];
    initArr.forEach((val, index) => {
        heapData.insert(val);
    });

    // console.log(heapData.getData())
    // debugger;
    for (var i = 0; i < initArr.length; i++) {
        // debugger;
        var result = heapData.extracMax();

        resultArr.unshift(result);
    }
    console.log(resultArr);
    return resultArr;
}

heapSort(initArr);