十大排序算法之堆排序

发表于 | 分类于
字数统计: 1.1k 字 | 阅读时长 ≈ 4 分钟

本文首发于个人博客

前言

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

  • 使用的语言为：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

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

代码地址：