堆排序

简述

堆排序是一种选择排序。

选择排序：每趟从待排序的记录中选出关键字最小的记录，顺序放在已排序的记录序列末尾，直到全部排序结束为止。

堆的简述

堆是一棵顺序存储的完全二叉树。

堆的种类

  • 其中每个结点的关键字都不大于其孩子结点的关键字，这样的堆称为小根堆（越走向孩子越大）
  • 其中每个结点的关键字都不小于其孩子结点的关键字，这样的堆称为大根堆（越走向孩子越小）

举例来说，对于n个元素的序列{R~0~, R~1~, … , R~n~}==当且仅当==满足下列关系之一时，称之为堆：（其中i=1,2,⋯,n/2向下取整）

  • R~i~ <= R~2i+1~ 且 R~i~ <= R~2i+2~ (小根堆)
  • R~i~ >= R~2i+1~ 且 R~i~ >= R~2i+2~ (大根堆)

序列R{3, 8, 15, 31, 25}是一个典型的小根堆。如图：
小根堆示意图
堆中有两个结点，元素3和元素8。
元素3在数组中以R[0]表示，它的左孩子结点是R[1]，右孩子结点是R[2]。
元素8在数组中以R[1]表示，它的左孩子结点是R[3]，右孩子结点是R[4]，它的父结点是R[0]

堆的特点

设当前元素在数组中以R[i]表示，那么，

  • 它的左孩子结点是：R[$2*i+1$];

  • 它的右孩子结点是：R[$2*i+2$];

  • 它的父结点是：R[$(i-1)/2$];

  • 是小根堆时：R[$i$] <= R[$2*i+1$] 且 R[$i$] <= R[$2i+2$]

  • 是大根堆时：R[$i$] >= R[$2*i+1$] 且 R[$i$] >= R[$2i+2$]

  • 设二叉树结点总数为 n，则最后一个非叶子结点是第 ?n/2? 个

  • 算法思想

    堆排序是利用==堆的性质==进行的一种选择排序
    一般步骤：

  • 根据初始数组去构造初始堆（构建一个完全二叉树，保证所有的父结点都比它的孩子结点数值大）。
  • 每次交换第一个和最后一个元素，输出最后一个元素（最大值），然后把剩下元素重新调整为大根堆。

从最低层次的叶子开始向上比较，比起父节点大就和父节点交换位置，但是与父节点交换位置后，父节点也要与再小一层的叶子比较是否需要再换位置
有可能会比较到最后一个节点才停止，而最后一个节点的判断方法再堆的特点中已经展示过了

时空间复杂度

时间复杂度

排序时间为 $O(nlogn)$。
堆的存储表示是顺序的。因为堆所对应的二叉树为完全二叉树，而完全二叉树通常采用顺序存储方式。
==当想得到一个序列中第k个最小的元素之前的部分排序序列，最好采用堆排序。==

空间复杂度

空间复杂度为 $O(1)$.

稳定性

堆排序是一种不稳定的排序方法。

因为在堆的调整过程中，关键字进行比较和交换所走的是该结点到叶子结点的一条路径，因此对于相同的关键字就可能出现排在后面的关键字被交换到前面来的情况。

源代码

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
#include <iostream>
#include <vector>

using namespace std;

void HeapAdjust(vector<int> &list, int parent, int length){
	int temp = list[parent];   // temp保存当前父节点
	int child = 2 * parent + 1;// 先获得左孩子

	while (child < length){
		// 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点
		if (child + 1 < length && list[child] < list[child + 1]){
			child++;
		}

		// 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点
		if (temp >= list[child]){
			break;
		}

		// 把孩子结点的值赋给父结点
		list[parent] = list[child];

		// 选取孩子结点的左孩子结点,继续向下筛选
		parent = child;
		child = 2 * parent + 1;
	}
	list[parent] = temp;
}

vector<int> HeadSort(vector<int> list){
	int length = list.size();
	// 循环建立初始堆
	for (int i = length / 2 - 1; i >= 0; i--){
		HeapAdjust(list, i, length);
	}

	// 进行n-1次循环，完成排序
	for (int i = length - 1; i > 0; i--){
		// 最后一个元素和第一元素进行交换
		int temp = list[i];
		list[i] = list[0];
		list[0] = temp;

		// 筛选 R[0] 结点，得到i-1个结点的堆
		HeapAdjust(list, 0, i);
	}
	return list;
}

int main(){
	int arr[] = { 6, 4, 8, 9, 2, 3, 1 };
	vector<int> test(arr, arr + sizeof(arr) / sizeof(arr[0]));
	cout << "排序前:";
	for (int i = 0; i < test.size(); i++){
		cout << test[i] << " ";
	}
	cout << endl;
	vector<int> result;
	result = HeadSort(test);
	cout << "排序后:";
	for (int i = 0; i < result.size(); i++){
		cout << result[i] << " ";
	}
}