十大排序算法之堆排序

本文首发于个人博客

前言

本系列排序包括十大经典排序算法。

  • 使用的语言为:Java
  • 结构为:
    定义抽象类Sort里面实现了,交换,大小比较等方法。例如交换两个值,直接传入下标就可以了。其他的具体排序的类都继承抽象类Sort。这样我们就能专注于算法本身。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*
* 返回值等于0,代表 array[i1] == array[i2]
* 返回值小于0,代表 array[i1] < array[i2]
* 返回值大于0,代表 array[i1] > array[i2]
*/
protected int cmp(int i1, int i2) {
return array[i1].compareTo(array[i2]);
}

protected int cmp(T v1, T v2) {
return v1.compareTo(v2);
}

protected void swap(int i1, int i2) {
T tmp = array[i1];
array[i1] = array[i2];
array[i2] = tmp;
}

什么是堆排序

  • 堆排序(Heap Sort)堆排序(英语:Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

堆的一些性质和结论

因为本文不是专门讲解堆这种数据结构的,主要是讲解堆排序算法的。所以这里只给出堆的一些性质和结论

最大堆、最小堆

  • 如果任意节点的值总是>=字节的的值,称为:最大堆、大根堆、 大顶堆
  • 如果任意节点的值总是<=字节的的值,称为:最小堆、小根堆、 小顶堆

索引i的规律(n是元素数量)

  • 如果i=0 它是根节点
  • 如果 2*i+1<=n-1 它的左子节点的索引为2*i+1
  • 如果 2*i+1>n-1 它没有左子节点
  • 如果 2*i+2<=n-1 它的右子节点的索引为2*i+2
  • 如果 2*i+2>n-1 它没有右子节点

算法稳定性

  • 堆排序不是一种稳定排序算法。

是否是原地算法

  • 何为原地算法?
    • 不依赖额外的资源或者依赖少数的额外资源,仅依靠输出来覆盖输入
    • 空间复杂度为 𝑂(1) 的都可以认为是原地算法
  • 非原地算法,称为 Not-in-place 或者 Out-of-place
  • 堆排序属于 In-place

代码

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
public class HeapSort <T extends Comparable<T>> extends Sort<T>{

private int heapSize;
@Override
protected void sort() {
// 原地建堆 自下而上的下滤
heapSize = array.length;
// heapSize>>1-1 第一个非叶子节点的下标
for (int i = (heapSize>>1)-1; i >=0; i--) {
siftDown(i);
}

while (heapSize>1) {
// 交换堆顶元素和尾部元素
swap(0, heapSize-1);
//堆顶元素最大放到尾部了。下次就不需要考虑这个了。所以size要减1
heapSize--;
// 下滤 维护堆的性质
siftDown(0);
}
}

//让index位置的元素下滤
private void siftDown(int index) {
// 取出要下滤的坐标的值
T element = array[index];
int half = heapSize>>1;
// 第一个叶子节点的索引 == 非叶子节点的数量
// index<第一个叶子节点的索引
// 必须保证index位置是非叶子节点
while (index<half) {
// index的节点有2种情况
// 1.只有左子节点
// 2.同时有左右子节点

// 默认为左子节点跟它进行比较
int childIndex = (index<<1)+1;
T child = array[childIndex];
// 右子节点
int rightIndex = childIndex +1;
// 选出左右子节点最大的那个
if (rightIndex<heapSize && cmp(array[rightIndex], child)>0) {
childIndex = rightIndex;
child = array[childIndex];
}

if (cmp(element, child)>=0) {
break;
}
// 将子节点存放到index位置
array[index]= child;
// 重新设置index
index = childIndex;
}
// 将目标值存放到最终的index位置
array[index] = element;

}
}

验证

数据源:从1到20000之间随机生成10000个数据来测试

Integer[] array = Integers.random(10000, 1, 20000);

结果如下:

【HeapSort】
稳定性:false 耗时:0.008s(8ms) 比较次数:23.54万 交换次数:9999

【BubbleSort】
稳定性:true 耗时:0.502s(502ms) 比较次数:4999.50万 交换次数:2489.42万

【SelectionSort】
稳定性:true 耗时:0.115s(115ms) 比较次数:4999.50万 交换次数:9999

可以看到堆排序明显比选择排序和冒泡排序的性能高很多。

代码地址:

------ 本文结束感谢您的阅读 ------