题解 | #O(nlogn)排序#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 将给定数组排序
 * @param arr int整型一维数组 待排序的数组
 * @return int整型一维数组
 */
function MySort( arr ) {
    // write code here
    let len = arr.length;
    if(len < 2) return;
    buildHeap(arr);
    
    for(let i = len - 1; i >= 0; i--) {
        swap(arr, 0, i);
        heapify(arr, i, 0);
    }
    
    return arr;
}

function swap(arr, index1, index2) {
    let temp = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = temp;
}
function buildHeap(arr) {
    let len = arr.length;
    for(let i = Math.floor(len/2); i >= 0; i--) {
        heapify(arr, len, i);
    }
}
function heapify(arr, len, cur){
    let maxChildIndex = cur * 2 + 1;
    while(maxChildIndex < len) {
        if(maxChildIndex + 1 < len && arr[maxChildIndex] < arr[maxChildIndex + 1]) {
            maxChildIndex += 1;
        }
        if(arr[cur] < arr[maxChildIndex]) {
            swap(arr, cur, maxChildIndex);
            cur = maxChildIndex;
            maxChildIndex = cur * 2 + 1;
        } else {
            break;
        }
    }
}
module.exports = {
    MySort : MySort
};

堆排序实现。

快拍或者堆排平均时间复杂度都为O(nlogn).