美文网首页
7、堆排序(Heap Sort)

7、堆排序(Heap Sort)

作者: Awanwan | 来源:发表于2018-10-10 18:19 被阅读10次

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

7.1 算法描述

  • 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆,此堆为初始的无序区;
  • 将堆顶元素R[1]与最后一个元素R[n]交换,此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n];
  • 由于交换后新的堆顶R[1]可能违反堆的性质,因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆,然后再次将R[1]与无序区最后一个元素交换,得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1,则整个排序过程完成。

7.2 动图演示

image

7.3 代码实现

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;
}

相关文章

  • JavaScript的排序算法——堆排序

    堆排序(Heap Sort) 堆排序(Heap Sort)是一种基于比较的排序算法。堆排序可以被认为是一种改进版的...

  • 7、堆排序(Heap Sort)

    堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆...

  • 堆排序(Heap Sort)

    1. 算法描述 堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构...

  • 堆排序(Heap Sort)

    一、算法概述 1.1 算法分类 十种常见排序算法可以分为两大类: 比较类排序:通过比较来决定元素间的相对次序,由于...

  • 堆排序(heap sort)

    堆排序可以认为是对选择排序的一种优化最好最坏平均时间复杂度:O(nlogn) 空间复杂度:O(1) 属于不稳定排序...

  • 3.2-选择排序-堆排序

    参考链接 选择排序:堆排序(Heap Sort) 白话经典算法系列之七 堆与堆排序 堆排序与快速排序,归并排序一样...

  • 03-堆排序(Heap Sort)

    堆排序(Heap Sort) 结合上一讲的内容,发现选择排序可以使用堆排序来进行优化。所以堆排序可以认为是对选择排...

  • iOS - 堆排序

    Demo_github 堆排序 堆排序(Heap Sort)是一种树形选择排序,是对直接选择排序的有效改进。 堆的...

  • 堆排序

    一、定义 堆排序(Heap Sort)是一种基于优先队列(堆实现)的排序方式。堆排序的步骤如下: 初始时待排序元素...

  • 堆排序

    预备知识 堆排序 堆排序(heap sort)是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的...

网友评论

      本文标题:7、堆排序(Heap Sort)

      本文链接:https://www.haomeiwen.com/subject/hldmaftx.html