堆排序:Javascript

奇妙的记忆点:

  • 不稳定
  • 内排序

    基本思想:

    分为两步,建堆与维持堆的性质,首先我们要先理解堆是什么东西.
    堆其实就是一个完全二叉树,我们可以使用顺序表存储一个二叉树,如下图所示来存储:

其中分为最大堆最小堆,而最大堆就是上头大,下头小;最小堆则反之.
明白了堆的定义我们就可以开始学习堆排序了,堆排序其实也是分为有序区与无序区,其中无序区就是我们建好的最大堆,根节点就是堆中最大的数,我们逐个让最大元素进有序区并对堆结构进行调整,维持根节点最大的性质,直到堆中元素清空为止,就是堆排序的过程.

堆排序关键代码

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
//工具函数
function swapItem(pre,next,arr){
var temp = arr[next];
arr[next] = arr[pre];
arr[pre] = temp;
}
function getLeft(i){
return 2*i+1;
}
function getRight(i){
return 2*i+2;
}
//维持堆的性质
function heapAdjust(arr,i,len){//数组,数组下标,堆元素长度(无序区长度)
var large,l = getLeft(i),r = getRight(i);
if(l < len&&arr[l] > arr[i]){
large = l;
}else{
large = i;
}
if(r < len&&arr[r] > arr[large]){
large = r;
}
//上述代码就是取节点也子节点三个元素之间的最大值
if(large !== i){
swapItem(large,i,arr);
heapAdjust(arr,large,len);//防止堆性质被破坏,所以递归调用来维持堆性质
}
}
//建堆
function heapBuild(arr,len){
for(var i = Math.floor(len / 2) - 1;i>=0;i--){
heapAdjust(arr,i,len);
}
//console.log(arr);
}
//堆排序本体如下
function heapSort(arr){
var heapSize = arr.length;//堆(无序区)大小
heapBuild(arr,heapSize);//建堆
for(var i=heapSize-1;i>=1;i--){
swapItem(0,i,arr);//堆顶部元素与堆底部元素交换(无序区->有序区)
//console.log(arr);
heapAdjust(arr,0,--heapSize);//维持堆性质(无序区)
}
}
//测试代码
var arr=[91,60,96,13,35,65,46,65,10,30,20,31,77,81,22];
heapSort(arr);
console.log(arr);

记忆点:

  • 最佳情况:T(n) = O(nlogn)
  • 最差情况:T(n) = O(nlogn)
  • 平均情况:T(n) = O(nlogn)