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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
| <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>堆排序</title>
<!--<link rel="stylesheet" type="text/css" href="../style/fdt.css" />-->
<script type="text/javascript" src="../js/jquery-1.6.2.min.js"></script>
<script type="text/javascript" src="../js/jquery.easydrag.handler.beta2.js"></script>
<script type="text/javascript">
$(document).ready(
function() {
// var array_1 = [9,8,7,6,5,4,3,2,1];
var array_1 = [4,5,3,1,2,0];
alert(array_1);
/*heapSort*/
alert(heapSort(array_1));
}
);
</script>
<style type="text/css">
* { padding:0; margin:0; }
body {
padding: 100px;
font-size: 15px;
}
</style>
<script type="text/javascript">
function heapSort(elements){
//调整函数
function headAdjust(elements, pos, len){
//将当前节点值进行保存
var swap = elements[pos];
//定位到当前节点的左边的子节点
var child = pos * 2 + 1;
//递归，直至没有子节点为止
while(child < len){
//如果当前节点有右边的子节点，并且右子节点较大的场合，采用右子节点和当前节点进行比较
if(child + 1 < len && elements[child] < elements[child + 1]){
child += 1;
}
//比较当前节点和最大的子节点，小于则进行值交换，交换后将当前节点定位于子节点上
if(elements[pos] < elements[child]){
elements[pos] = elements[child];
pos = child;
child = pos * 2 + 1;
}
else{
break;
}
elements[pos] = swap;
}
}
//构建堆
function buildHeap(elements){
//从最后一个拥有子节点的节点开始，将该节点连同其子节点进行比较，
//将最大的数交换与该节点,交换后，再依次向前节点进行相同交换处理，
//直至构建出大顶堆（升序为大顶，降序为小顶）
for(var i=elements.length/2; i>=0; i--){
headAdjust(elements, i, elements.length);
}
}
function sort(elements){
//构建堆
buildHeap(elements);
//从数列的尾部开始进行调整
for(var i=elements.length-1; i>0; i--){
//堆顶永远是最大元素，故，将堆顶和尾部元素交换，将
//最大元素保存于尾部，并且不参与后面的调整
alert(elements);
var swap = elements[i];
elements[i] = elements[0];
elements[0] = swap;
alert(elements);
//进行调整，将最大的元素调整至堆顶
headAdjust(elements, 0, i);
alert(elements);
}
}
sort(elements);
return elements;
}
</script>
</head>
<body>
堆排序
</body>
</html>
|
