数据结构与算法系列(7)--堆排序

这一篇文章主要介绍二叉堆的概念，以及堆排序算法

二叉堆

二叉堆其实就是由一个数组数据表示出来的一个完全二叉树，树的内容在后序讲述，二叉堆需要满足的仅仅是父节点的值大于两个子节点

为了方便计算，第一个元素默认为在1号位置，当然这个数据可以进行转换

堆排序

堆排序的核心在于将数组构建成一个有序的堆，然后通过提取堆的顶部(最大值)–维护的循环来对堆进行排序

构造有序堆

构造有序堆只需要将元素一个个遍历(一个个加入到堆当中)，然后进行上浮即可，也就是元素与自己的父元素进行比较，然后如果大于父元素就进行交换，并重复操作直到不满足或者到顶

下沉

在堆构造完成后，就能直接获取最大元素，在获取最大元素后只要将其与堆的末尾元素交换，然后末尾的位置不纳入堆的范围即可，同时使用下沉操作，来将置换上来的小值向下交换，维持堆的循序结构

堆排序实现

function StackSort(arr){
    //上浮
    function swim(arr, p){
        while (p > 1 && arr[p] > arr[parseInt(p / 2)]){
            [arr[p], arr[parseInt(p / 2)]] = [arr[parseInt(p / 2)], arr[p]] 
            p = parseInt(p / 2)
        }
    }

    //下沉--将第一个元素下沉
    function sink(arr, i, len){
        while (2 * i <= len){
            let j = 2 * i
            if (j < len && arr[j] < arr[j + 1]) j++
            if (arr[i] < arr[j]){
                [arr[i], arr[j]] = [arr[j], arr[i]]
                i = j
            } else {
                break
            }
        }
    }

    let length = arr.length
    for (let i = length - 1; i >= 0; i--){
        arr[i + 1] = arr[i]
    }

    for (let i = 0; i < length; i++){
        swim(arr, i + 1)
    }

    for (let i = length; i > 1; i--){
        [arr[1], arr[i]] = [arr[i], arr[1]]
        sink(arr, 1, i - 1)
    }

    for (let i = 0; i < length; i++){
        arr[i] = arr[i + 1]
    }
    arr.length = length

    return arr
}

除此之外，堆的初始化还可以通过下沉来完成

function StackSort2(arr){
    //下沉--将第一个元素下沉
    function sink(arr, i, len){
        while (2 * i <= len){
            let j = 2 * i
            if (j < len && arr[j] < arr[j + 1]) j++
            if (arr[i] < arr[j]){
                [arr[i], arr[j]] = [arr[j], arr[i]]
                i = j
            } else {
                break
            }
        }
    }

    let length = arr.length
    for (let i = length - 1; i >= 0; i--){
        arr[i + 1] = arr[i]
    }

    for (let i = parseInt(length / 2); i >= 1; i--){
        sink(arr, i, length)
    }

    for (let i = length; i > 1; i--){
        [arr[1], arr[i]] = [arr[i], arr[1]]
        sink(arr, 1, i - 1)
    }

    for (let i = 0; i < length; i++){
        arr[i] = arr[i + 1]
    }
    arr.length = length

    return arr
}

算法属性

最优时间复杂度	平均时间复杂度	最差时间复杂度	空间复杂度	稳定性
Ω(nlogn)	Θ(nlogn)	O(nlogn)	O(1)	不稳定

END

2019-03-05 完成

2019-03-04 立项