我们已经准备好了,你呢?

2020我们与您携手共赢,为您的企业形象保驾护航!

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法:

  1. 大顶堆:每个节点的值都大于或等于其子节点的值,在堆排序算法中用于升序排列;
  2. 小顶堆:每个节点的值都小于或等于其子节点的值,在堆排序算法中用于降序排列;

堆排序的平均时间复杂度为 Ο(nlogn)。

1. 算法步骤

  1. 创建一个堆 H[0……n-1];

  2. 把堆首(更大值)和堆尾互换;

  3. 把堆的尺寸缩小 1,并调用 shift_down(0),目的是把新的数组顶端数据调整到相应位置;

  4. 重复步骤 2,直到堆的尺寸为 1。

2. 动图演示


代码实现

JavaScript

实例

var len;    // 因为声明的多个函数都需要数据长度,所以把len设置成为全局变量

function buildMaxHeap(arr) {   // 建立大顶堆
    len = arr.length;
    for (var i = Math.floor(len/2); i >= 0; i--) {
        heapify(arr, i);
    }
}

function heapify(arr, i) {     // 堆调整
    var left = 2 * i + 1,
        right = 2 * i + 2,
        largest = i;

    if (left < len && arr[left] > arr[largest]) {
        largest = left;
    }

    if (right < len && arr[right] > arr[largest]) {
        largest = right;
    }

    if (largest != i) {
        swap(arr, i, largest);
        heapify(arr, largest);
    }
}

function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

function heapSort(arr) {
    buildMaxHeap(arr);

    for (var i = arr.length-1; i > 0; i--) {
        swap(arr, 0, i);
        len--;
        heapify(arr, 0);
    }
    return arr;
}
我们凭借多年的网站建设经验,坚持以“帮助中小企业实现网络营销化”为宗旨,累计为1000多家客户提供品质建站服务,得到了客户的一致好评。如果您有网站建设网站改版百度优化、名注册、主机空间、手机网站建设公众号开发小程序制作、网站备案等方面的需求...
请立即点击咨询我们或拨打咨询热线: 13820372851,我们会详细为你一一解答你心中的疑难。项目经理在线

我们已经准备好了,你呢?

2020我们与您携手共赢,为您的企业形象保驾护航!

在线客服
联系方式

热线电话

13820372851

上班时间

周一到周五

公司电话

022-26262675

二维码
线
在线留言