JavaScript经典排序算法——堆排序

╰+哭是因爲堅強的太久メ 2022-05-26 07:10 133阅读 0赞

**堆是具有以下性质的完全二叉树：**

**  每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；**

**每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。**

**如下图：**

![WEBRESOURCE4e087210e7e30a78775fbaf73068d3a5][]

**同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子：**

![WEBRESOURCE97e099e3cbcc45353d15e77996ffe282][]

该数组从逻辑上讲就是一个堆结构，用简单的公式描述一下堆的定义就是：

大顶堆：arr\[i\] >= arr\[2i+1\] OR arr\[i\] >= arr\[2i\]

小顶堆：arr\[i\] <= arr\[2i+1\] OR arr\[i\] <= arr\[2i\]

## **效率：** ##

时间复杂度：O(nlog2n)

空间复杂度： O(1)

## **稳定性**：不稳定 ##

## **JavaScript代码实现：**   ##

function heapSort(array) {
        var temp;
        var i;
        var result = "";
        for (i = Math.floor(array.length / 2); i >= 0; i--) {
            heapAdjust(array, i, array.length - 1); //将数组array构建成一个大顶堆
        }
        for (i = array.length - 1; i >= 0; i--) {
            /*把根节点交换出去*/
            temp = array[i];
            array[i] = array[0];
            array[0] = temp;
            /*余下的数组继续构建成大顶堆*/
          heapAdjust(array, 0, i - 1);
            /* 输出结果 */
            result += "<br />第" + (array.length - i).toString() + "遍排序的结果是:";
            for (var n = 0; n < array.length; n++) {
                result += array[n] + ",";
            }
            /* 输出结果结束 */
        }
        return result;
    }
    //要调整的子树
    //start为数组开始下标
    //max是数组结束下标
    function heapAdjust(array, start, max) {
        var temp, j;
        temp = array[start];//temp是根节点的值
        for (j = 2 * start; j < max; j *= 2) {
            if (j < max && array[j] < array[j + 1]) {  //取得较大孩子的下标
                ++j;
            }
            if (temp >= array[j])
                break;
                array[start] = array[j];
                start = j;
        }
        array[start] = temp;
    }
     
    var array = [50,45,40,20,25,35,30,10,15];
    console.log(heapSort(array));    //10,15,20,25,30,35,40,45,50

[WEBRESOURCE4e087210e7e30a78775fbaf73068d3a5]: https://note.youdao.com/yws/res/3717/WEBRESOURCE4e087210e7e30a78775fbaf73068d3a5
[WEBRESOURCE97e099e3cbcc45353d15e77996ffe282]: https://note.youdao.com/yws/res/3722/WEBRESOURCE97e099e3cbcc45353d15e77996ffe282

发表评论取消回复

表情：

评论列表（有 0 条评论，133人围观）

还没有评论，来说两句吧...

相关阅读

相关 php+堆排序算法,10大经典排序算法之堆排序（PHP版）

堆排序，是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于(或者大于)它的父节点。大顶堆升序，小顶堆降

刺骨的言语ヽ痛彻心扉/ 2022年11月12日 10:54/ 0 赞/ 192 阅读

相关排序算法——堆排序

前言对于推排序它像合并排序而不像插入排序，堆排序的运行时间为O(nlogn)。像插入排序而不像合并排序，它是一种原地排序算法：在任何时候，数组中只有常数和元素存储在输入

ゝ一纸荒年。/ 2022年06月12日 00:00/ 0 赞/ 177 阅读

相关 JavaScript经典排序算法——计数排序

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。就是遍历数组记录数组下的元素出现

青旅半醒/ 2022年05月26日 12:14/ 0 赞/ 165 阅读

相关 JavaScript经典排序算法——归并排序

“归并”的意思是将两个或两个以上的有序表组合成一个新的有序表。假如初始序列含有n个记录，则可看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到\[n/2\]（向上

柔情只为你懂/ 2022年05月26日 12:10/ 0 赞/ 166 阅读

相关 JavaScript经典排序算法——堆排序

堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图： ![

╰+哭是因爲堅強的太久メ/ 2022年05月26日 07:10/ 0 赞/ 134 阅读

相关 JavaScript经典排序算法——选择排序

选择排序的基本思想是：每一趟在n-i+1（i=1,2,3……，n-1）个记录中选取关键字最小的记录作为有序序列中第i个记录。选择排序的比较次数与初始元素顺序无关，它的最好、最坏

亦凉/ 2022年05月26日 05:54/ 0 赞/ 149 阅读

相关 JavaScript经典排序算法——快速排序

快速排序是对冒泡排序的一种改进。基本思想是：通过一趟排序将待排序列分割成独立的两部分，其中一部分序列均比另一部分序列的元素小，则可分别对这两部分序列继续进行排序，以达到整个序列

╰半夏微凉°/ 2022年05月26日 05:06/ 0 赞/ 133 阅读

相关 JavaScript经典排序算法——冒泡排序

冒泡排序是一种简单的排序算法。它重复的走访要排序的数列，首先将第一个元素和第二个元素进行比较，若为逆序（Ri>Rj），则将两个元素互换，然后比较第二个元素与第三个元素，以此类推

Love The Way You Lie/ 2022年05月26日 04:52/ 0 赞/ 153 阅读

相关排序算法：堆排序

一、前言堆排序是一种选择排序。选择排序：每趟从待排序的记录中选出关键字最小的记录，顺序放在已排序的记录序列末尾，直到全部排序结束为止。 ----

秒速五厘米/ 2022年04月04日 11:00/ 0 赞/ 265 阅读

相关排序算法---堆排序

二叉堆是完全二叉树或者是近似完全二叉树。二叉堆满足二个特性： 1．父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值。 2．每个结点的左子树和右子树都是一个二

以你之姓@/ 2022年03月11日 06:06/ 0 赞/ 267 阅读