-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path堆排序.html
56 lines (56 loc) · 2.61 KB
/
堆排序.html
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8" />
<title>Document</title>
</head>
<body></body>
<script>
// 待调整的堆 要下沉的父节点 堆的有效大小
function downAdjust(array, parentIndex, length) {
// temp 保存父节点的值 用于最后的赋值
var temp = array[parentIndex];
var childIndex = 2 * parentIndex + 1; // 左孩子下标
while (childIndex < length) {
// 如果有右孩子，且右孩子大于左孩子的值 则定位到右孩子
if (
childIndex + 1 < length &&
array[childIndex + 1] > array[childIndex]
) {
childIndex++;
}
// 如果父节点大于任何一个孩子的值，则直接跳出
if (temp >= array[childIndex]) {
break;
}
// 无需真正交换 单向赋值即可 因为比较还没有结束
// 父节点下面的子节点还会可能有子节点 需要接着比较 所以不能直接将父子节点的值直接交换
array[parentIndex] = array[childIndex]; // 子节点中值大的上浮
parentIndex = childIndex; // 子节点的索引赋给父节点索引
childIndex = 2 * childIndex + 1; // 计算子节点有没有子节点 没有值会超出length 本次循环结束
}
array[parentIndex] = temp; // 在这里将原来父节点的值替换到子节点中 parentIndex是原来值大子节点的索引
}
function heapSort(array) {
// 把无序数组构建成最大堆
// 从最后一个非叶子节点开始 依次比较
// Math.ceil((array.length-2)/2)最后一个非叶子节点的下标
for (var i = Math.ceil((array.length - 2) / 2); i >= 0; i--) {
downAdjust(array, i, array.length);
}
// 循环调整堆顶元素 移到集合尾部 调整堆产生新的堆顶
// 最大堆堆顶是堆中最大的元素，第一次直接将该元素和第一个元素调换位置，将除最后一个元素外的剩下元素再构建成最大堆，这样第二轮中第二大的元素就会成为堆顶，然后将第二大元素与倒数第二个元素交换位置，以此类推。数组最后就会成为升序数组
for (var i = array.length - 1; i > 0; i--) {
// 最后一个元素和第一个元素进行交换
var temp = array[i];
array[i] = array[0];
array[0] = temp;
// 除去已经调整的元素，将剩下的元素重新调整为最大堆
downAdjust(array, 0, i);
}
return array;
}
var arr = [1, 3, 2, 6, 5, 7, 8, 9, 10, 0];
console.log(heapSort(arr));
</script>
</html>