排序算法:堆排序

堆(heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质:

  1. 堆中某个结点的值总是不大于或不小于其父结点的值;
  2. 堆总是一棵完全二叉树。

将根结点最大的堆叫做最大堆或大根堆,根结点最小的堆叫做最小堆或小根堆。

例如:

构建堆

数组和堆的特点

  1. 使用一维数组来表示一个堆,下标从0~n,0表示堆顶
  2. 如果一个节点的下标为x,那么左子节点的下标为 2x+1,右子节点的下标为2x+2
  3. 如果一个节点的下标为x,那么父节点的下标为(x-1)/2

堆化

在一个已经是最大堆(或者最小堆)的末尾插入一个数据,有可能会打破这个最大堆(或者最小堆)

如下图,在一个最大堆末尾插入一个14的数据,就打破了这个最大堆。这时需要进行堆化处理。

处理方式就是,用这个插入的节点和其父节点对比,如果比父节点大,则互相交换。

交换后再继续和其父节点比较,直至堆顶。

构建堆

由于堆的节点和数组下标有着明显的对应特征,所以构建一个堆只需要固定的几个临时变量,空间复杂度只有O(1)。

构建一个堆也比较简单:

  1. 首先认为下标0的数据为堆顶
  2. 接着认为向这个最大堆(或者最小堆)的末尾(首次下标是1)插入数据
  3. 处理这个新插入的数,使数据堆化
  4. 重复2~3的步骤,直至数组最后一个元素

需要注意的是:如果要升序排序,则需要构建最大堆,如果要降序排序,则需要构建最小堆

排序

排序步骤也比较简单,就是在执行剔除堆顶的操作

  1. 交换堆顶(下标为0)的数据和数组最后一个(首次下标为n)的数据,此时最后一个数据是已升序排列完的数据
  2. 由于步骤1,导致打破了最大堆(或者最小堆),执行堆化操作
  3. 再重复1~2 直至整个堆只剩下堆顶一个数据为止

示意图

时间复杂度和空间复杂度

堆的构建时间复杂度:O(n2)
排序时间复杂度:O(nlogn)

稳定性

由于对序列跳跃式维护堆的结构性质,相同值顺序无法得到保障,所以堆排序是不稳定的。

代码

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
public void sort(int[] nums){
buildHeap(nums);
int point = nums.length - 1;
while(point > 0){
int temp = nums[0];
nums[0] = nums[point];
nums[point] = temp;
heapity(nums,point);
point--;
}
}

private void heapity(int[] nums, int point) {
int index = 0;
while(index <= point){
int left = 2 * index + 1;
int right = left +1;
if(left >= point){
//超出界限
return;
}else if(right >= point){
//右子节点超出边界
if(nums[left] > nums[index]){
int temp = nums[left];
nums[left] = nums[index];
nums[index] = temp;
index = left;
}else{
return;
}
}else{
if(nums[left] >= nums[right] && nums[left] > nums[index]){
int temp = nums[left];
nums[left] = nums[index];
nums[index] = temp;
index = left;
}else if(nums[right] >= nums[left] && nums[right] > nums[index]){
int temp = nums[right];
nums[right] = nums[index];
nums[index] = temp;
index = right;
}else{
return;
}
}
}
}

private void buildHeap(int[] nums) {
for (int i = 1; i < nums.length; i++) {
buildHeap(nums,i);
}
}

private void buildHeap(int[] nums,int index) {
while(index > 0 ) {
int parentIndex = (index-1) / 2;
if (nums[parentIndex] < nums[index]) {
int temp = nums[parentIndex];
nums[parentIndex] = nums[index];
nums[index] = temp;
index = parentIndex;
} else {
return;
}
}
}