题解 | #排序#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 将给定数组排序
 * @param arr int整型一维数组 待排序的数组
 * @return int整型一维数组
 */
function MySort(array) {
    // 构建初始大顶堆
    for(let i = 0;i < array.length;i++){
        startheapSort(array,i)
    }
    //更新大顶堆
    let size = array.length
    //交换首位和末尾
    swap(array,0,--size)
    while (size > 0){
        againheapSort(array,0,size)
        swap(array,0,--size)
    }
    return array
}
//初始大顶堆函数——根节点大于左右孩子节点
const startheapSort = function (array,index) {
    //遍历数组构成的初始二叉树
    //判断当前元素和父节点(当前元素下标i和父节点下标j的关系：j = i-1/2)的大小，小于进行交换
    // 由子节点推断父节点下标
    while (array[index] > array[parseInt((index-1)/2)]){
        swap(array,index,parseInt((index-1)/2))
        // 将索引变成父节点
        index = parseInt((index-1)/2)
    }
    }
//数组中任意两个下标为i，j的元素进行交换的函数
const swap = function (array,i,j) {
    let temp = array[i]
    array[i] = array[j]
    array[j] = temp
    return array
}
//更新大顶堆
const againheapSort = function(array,index,size){
    let left = 2*index+1
    while (left < size){
        //判断左右节点的大小
        let largest = left+1 < size && array[left] < array[left+1] ? left+1 : left;
    //    判断父节点和左右节点的大小
        largest = array[index] < array[largest]? largest : index
        if(largest === index)break;
        swap(array,index,largest)
        index = largest
        left = 2*index + 1
    }
    return array
}
module.exports = {
    MySort: MySort,
};

解题思路

堆排序：时间复杂度为O(logN)

堆排序主要分两个步骤：

（1）将待排序列初建一个大顶堆：

具体地，从数组第一个元素开始依次判断当前元素和其父节点元素的大小，父节点索引由子节点的索引index得到（(index-1)/2）;大于父节点值就将两个进行交换，将索引变成父节点，索引index++,再进行判断。

（2）更新大顶堆

1. 将首位和末尾交换位置并将数组长度减一，表示数组末尾已是最大值，不需要再比较大小；
2. 对比左右节点哪个大，然后记住大的节点的索引并且和父节点对比大小，如果子节点大就交换位置；
3. 重复以上操作 1 - 2 直到整个数组都是大根堆。