Fork me on GitHub

堆排序详细分析

发表于 | 分类于 |
| 字数统计 942 | 阅读时长 4

堆排序

利用数据结构最大堆和最小堆进行排序操作。升序排序利用最大堆，降序排序利用最小堆。

基本思路（升序为例）

  • 初始化堆：将数列a[1…n]构造成最大堆。

  • 交换数据：将a[1]和a[n]交换，使a[n]是a[1…n]中的最大值；然后将a[1…n-1]重新调整为最大堆。 接着，将a[1]和a[n-1]交换，使a[n-1]是a[1…n-1]中的最大值；然后将a[1…n-2]重新调整为最大值。 依次类推，直到整个数列都是有序的。

  • 数组实现二叉堆有以下性质（第一个数组元素索引值为0）：

    索引为i的左孩子的索引是 (2*i+1);

    索引为i的左孩子的索引是 (2*i+2);

    索引为i的父结点的索引是 floor((i-1)/2);

时间复杂度与稳定性

时间复杂度

堆排序的时间复杂度是O(N*lgN)。

堆排序是采用的二叉堆进行排序的，二叉堆就是一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的定义，它的深度至少是lg(N+1)。最多是多少呢？由于二叉堆是完全二叉树，因此，它的深度最多也不会超过lg(2N)。因此，遍历一趟的时间复杂度是O(N)，而遍历次数介于lg(N+1)和lg(2N)之间；因此得出它的时间复杂度是O(N*lgN)。

稳定性

堆排序是不稳定性算法。在交换数据的时候，是比较父结点和子节点之间的数据，所以，即便是存在两个数值相等的兄弟节点，它们的相对顺序在排序也可能发生变化。

适用情况

对较大的序列排序，时间复杂度同快速排序、归并排序，特长所需辅助空间少，适合相对有序的序列排序。

堆排序实现

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include<iostream>
using namespace std;
//最大堆建堆子步骤（堆的调整）
void buildMaxHeap(int *a, int p, int q)
{
	int s = p;
	int l = 2 * s + 1;
	int tmp = a[s];
	for (; l <= q; s = l, l = 2 * s + 1)
	{
		if (l != q && a[l] < a[l + 1])
		{
			l++;
		}
		if (tmp < a[l])
		{
			a[s] = a[l];
			a[l] = tmp;
		}
		else
		{
			break;
		}
	}
}
//堆排序（升序）
void heapSortA(int * a, int n)
{
	int tmp;
	//从最后一个非叶子节点-->0 依次调整，调整结束，数组成为最大堆（建堆）。
	for (int i = n / 2 - 1; i >= 0; i--)
	{
		buildMaxHeap(a, i, n - 1);
	}
	for (int i = n - 1; i > 0; i--)
	{
		//交换堆顶元素和堆最后的元素，并将堆的范围缩小1
		tmp = a[0];
		a[0] = a[i];
		a[i] = tmp;
		//调整剩下的堆元素，使之为最大堆
		buildMaxHeap(a, 0, i-1);
	}
}
//最小堆建堆子步骤（堆的调整）
void buildMinHeap(int *a, int p, int q)
{
	int s = p;
	int l = 2 * s + 1;
	int tmp = a[s];
	for (; l <= q; s = l, l = 2 * s + 1)
	{
		if (l != q && a[l] > a[l + 1])
		{
			l++;
		}
		if (tmp > a[l])
		{
			a[s] = a[l];
			a[l] = tmp;
		}
		else
		{
			break;
		}
	}
}
//堆排序（降序）
void heapSortD(int * a, int n)
{
	int tmp;
	//从最后一个非叶子节点-->0 依次调整，调整结束，数组成为最小堆（建堆）。
	for (int i = n / 2 - 1; i >= 0; i--)
	{
		buildMinHeap(a, i, n - 1);
	}
	for (int i = n - 1; i > 0; i--)
	{
		//交换堆顶元素和堆最后的元素，并将堆的范围缩小1
		tmp = a[0];
		a[0] = a[i];
		a[i] = tmp;
		//调整剩下的堆元素，使之为最小堆
		buildMinHeap(a, 0, i - 1);
	}
}
int main()
{
	int a[] = { 10, 50, 90, 60, 70, 120, 80, 20, 100, 30, 40 };
	int n = 11;
	for (int i = 0; i < n; i++)
	{
		cout << a[i] << "  ";
	}
	cout << endl;
	heapSortA(a, n);
	for (int i = 0; i < n; i++)
	{
		cout << a[i] << "  ";
	}
	cout << endl;
	heapSortD(a, n);
	for (int i = 0; i < n; i++)
	{
		cout << a[i] << "  ";
	}
	cout << endl;
	return 0;
}

输出结果：

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