JavaScirpt基础-数组排序之堆排序

简介: 堆排序

堆排序

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。

堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

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

堆的底层实际上就是一棵完全二叉树,可以用数组实现。

根节点最大的堆叫作大根堆,根节点最小的堆叫作小根堆,可以根据从大到小排序或者从小到大来排序,分别建立对应的堆就可以。

var a = [1, 3, 8, 6, 15, 3, 4, 23, 76, , 34, 232, 6, 9, 456, 221];

function heap_sort(arr) {

var len = arr.length

var k = 0

function swap(i, j) {

var temp = arr[i]

arr[i] = arr[j]

arr[j] = temp

}

function max_heapify(start, end) {

var dad = start

var son = dad * 2 + 1

if (son >= end) return

if (son + 1 < end && arr[son] < arr[son + 1]) {

  son++

}

if (arr[dad] <= arr[son]) {

  swap(dad, son)

  max_heapify(son, end)

}

}

for (var i = Math.floor(len / 2) - 1; i >= 0; i--) {

max_heapify(i, len)

}

for (var j = len - 1; j > k; j--) {

swap(0, j)

max_heapify(0, j)

}

return arr

}

heap_sort(a); // [, 1, 3, 3, 4, 6, 6, 8, 9, 15, 23, 34, 76, 221, 232, 456]

目录
相关文章
|
1月前
|
存储 搜索推荐 算法
【用Java学习数据结构系列】七大排序要悄咪咪的学(直接插入,希尔,归并,选择,堆排,冒泡,快排)以及计数排序(非比较排序)
【用Java学习数据结构系列】七大排序要悄咪咪的学(直接插入,希尔,归并,选择,堆排,冒泡,快排)以及计数排序(非比较排序)
22 1
|
6月前
|
算法
桶排序(简化版)与冒泡排序
桶排序(简化版)与冒泡排序
36 0
|
6月前
|
C语言
【汇编语言实战】使用插入排序对给定的数组排序(用栈传递参数)
【汇编语言实战】使用插入排序对给定的数组排序(用栈传递参数)
39 1
|
6月前
|
算法 搜索推荐 C语言
C语言数据结构之排序整合与比较(冒泡,选择,插入,希尔,堆排序,快排及改良,归并排序,计数排序)
C语言数据结构之排序整合与比较(冒泡,选择,插入,希尔,堆排序,快排及改良,归并排序,计数排序)
|
6月前
|
算法 测试技术 C#
【二分查找】自写二分函数的总结
【二分查找】自写二分函数的总结
|
6月前
|
JavaScript 搜索推荐 前端开发
JS数组自定义排序方法,冒泡排序、插入排序、选择排序和快速排序。
JS数组自定义排序方法,冒泡排序、插入排序、选择排序和快速排序。
70 0
|
算法 搜索推荐 Shell
Shell编程之数组排序算法(冒泡排序、直接选择排序、反转排序)
1、数组排序(使用tr、sort、for) 操作步骤; 使用tr命令将数组内每个元素之间的空格替换为换行符; 之后使用sort命令按从小到大重新排序; 最后使用for循环遍历排序后的元素值。
477 0
|
存储 算法 搜索推荐
数据结构各内部排序算法总结对比及动图演示(插入排序、冒泡和快速排序、选择排序、堆排序、归并排序和基数排序等)1
数据结构各内部排序算法总结对比及动图演示(插入排序、冒泡和快速排序、选择排序、堆排序、归并排序和基数排序等)1
195 0
|
算法 搜索推荐