文章目录
  1. 1. 堆排序
    1. 1.1. 排序问题
    2. 1.2.
    3. 1.3. 思路
    4. 1.4. js基本思路实现
    5. 1.5. 验证

堆排序的javascript实现。

堆排序


排序问题

  • 输入:n个数的一个序列<a1, a2, ..., an>
  • 输出:输入序列的一个排列<a1', a2', ..., an'>,满足a1' <= a2' <= ... <= an'

堆(二叉堆)可以视为一棵完全的二叉树,完全二叉树的一个“优秀”的性质是,除了最底层之外,每一层都是满的,这使得堆可以利用数组来表示(普通的一般的二叉树通常用链表作为基本容器表示),每一个结点对应数组中的一个元素。

二叉堆一般分为两种:最大堆和最小堆。

  • 最大堆:

    • 最大堆中的最大元素值出现在根结点(堆顶)
    • 堆中每个父节点的元素值都大于等于其孩子结点(如果存在)
  • 最小堆:

    • 最小堆中的最小元素值出现在根结点(堆顶)
    • 堆中每个父节点的元素值都小于等于其孩子结点(如果存在)

通常堆是通过一维数组来实现的。在数组起始位置为0的情形中:

父节点i的左子节点在位置(2*i+1)
父节点i的右子节点在位置(2*i+2)
子节点i的父节点在位置floor((i-1)/2)

思路

堆排序就是把最大堆堆顶的最大数取出,将剩余的堆继续调整为最大堆,再次将堆顶的最大数取出,这个过程持续到剩余数只有一个时结束。在堆中定义以下几种操作:

  • 最大堆调整(Max-Heapify):将堆的末端子节点作调整,使得子节点永远小于父节点
  • 创建最大堆(Build-Max-Heap):将堆所有数据重新排序,使其成为最大堆
  • 堆排序(Heap-Sort):移除位在第一个数据的根节点,并做最大堆调整的递归运算

参考堆排序-wiki

js基本思路实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
function swap(arr, a, b) {
if (a == b) { return; }
var c = arr[a];
arr[a] = arr[b];
arr[b] = c;
}
function heapSort(iArr) {
var n = iArr.length;
// 若只有一个或者没有,则返回
if (n <= 1) { return iArr; }
// 若有多个,则建最大堆
else {
// 建堆(Build-Max-Heap)
for (var i = Math.floor(n / 2); i >= 0; i--) {
maxHeapify(iArr, i, n);
}
// 堆排序
for (var j = 0; j < n; j++) {
swap(iArr, 0, n - 1 - j)
maxHeapify(iArr, 0, n - 2 - j);
}
return iArr;
}
}
function maxHeapify(Arr, i, size) {
var l = 2 * i + 1, r = 2 * i + 2; // 左子节点为2i + 1,右子节点为2i + 2
var largest = i;
// 若子节点比节点大,则标记
if (l <= size && Arr[l] > Arr[largest]) {
largest = l;
}
if (r <= size && Arr[r] > Arr[largest]) {
largest = r;
}
// 若标记有子节点,则交换父子位置,并递归计算
if (largest !== i) {
swap(Arr, i, largest);
maxHeapify(Arr, largest, size);
}
}

验证

1
2
3
4
5
6
7
8
heapSort([5, 2, 4, 6, 1, 3]);
// 输出[1, 2, 3, 4, 5, 6]
heapSort([2, 1, 3, 1, 5]);
// 输出[1, 1, 2, 3, 5]
heapSort([5, 2, 12, 2, 134, 1, 3, 34, 4, 6, 1, 3, 4]);
// 输出[1, 1, 2, 2, 3, 3, 4, 4, 5, 6, 12, 34, 134]

查看Github有更多内容噢:https://github.com/godbasin
更欢迎来被删的前端游乐场边撸猫边学前端噢

码生艰难,写文不易,给我家猪囤点猫粮了喵~

作者:被删

出处:https://godbasin.github.io

本文版权归作者所有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。

文章目录
  1. 1. 堆排序
    1. 1.1. 排序问题
    2. 1.2.
    3. 1.3. 思路
    4. 1.4. js基本思路实现
    5. 1.5. 验证