数据结构与算法_排序算法_三个高级排序算法性能对比

堆排序，快排，归并排序算法性能分析

比较三个高级排序算法的性能，分别是归并排序，希尔排序和堆排序，这三个排序算法的时间性能分析表如下：

堆排序：上浮调整是O(logn) ，将元素进行交换O(n)；最好情况下，没有占用额外的空间，空间复杂度O(1);
快速排序：平均时间复杂度：O(nlogn),根据基准数将数列分成两半，时间复杂地O(n)；递归O(logn); 最坏情况下时间复杂度：O(n^2)，即数据基本趋于有序。
归并排序：归的过程中O(logn)，将数据合并O(n)，所以时间复杂度O(lognn)；空间复杂度O(n);

下面的代码分别测试了三个排序算法，对800万和8000万个数据进行排序后的时间对比：可以看到快速排序是最时间最少，其次是归并排序，最后是堆排序。

问题：从上面的性能分析表中可以看到，这三个算法的时间复杂度都是O(logn*n)，为什么时间相差很大呢？

主要原因有两个：

1. 快排和归并排序，在遍历元素时候都是按照顺序遍历的，对CPU缓存是友好的（CPU缓存命中率高），但是堆排序是按照父子节点的关系进行数据的上浮或下沉调整，即操作数组时候，元素不是按顺序操作的，根据程序局部性原理，这样操作效率就低。
2. 堆排序的过程中，以大根堆为例，将堆顶元素与堆末尾元素交换后，将堆顶的元素进行下沉调整，堆顶的小元素一直下沉到最下边，中间的过程做了很多无效的比较操作，影响了算法效率。

代码

#include 
#include 


using namespace std;
void MergeS(int arr[], int begin, int mid, int end, int *p)
{

	int i = begin;
	int j = mid + 1;
	int index = 0;
	// 将比较的两个小数列按序合成一个大数列
	while (i <= mid && j <= end)
	{
		if (arr[i] <= arr[j])
		{
			p[index++] = arr[i++];
		}
		else
		{
			p[index++] = arr[j++];
		}
	}

	// 如果右边的元素都放进去了，把左边的元素放入临时数组中
	while (i <= mid)
	{
		p[index++] = arr[i++];
	}
	// 同理将右边数据放入临时数组中
	while (j <= end)
	{
		p[index++] = arr[j++];
	}

	// 最后将临时空间中的数据放入原数组中
	for (i = begin, index = 0; i <= end; i++, index++)
	{
		arr[i] = p[index];
	}
	// 最后删除 临时空间 

}

void MergeSort1(int arr[], int begin, int end, int *p)
{
	if (begin >= end)
	{
		return;
	}
	int mid = (begin + end) / 2;
	// 先递 
	MergeSort1(arr, begin, mid, p);
	MergeSort1(arr, mid + 1, end, p);

	// 开始处理归
	// 对树中的数据进行排序并合并
	MergeS(arr, begin, mid, end, p);
}

void MergeSort1(int arr[], int size)
{
	int *p = new int[size];
	MergeSort1(arr, 0, size - 1, p);
	delete[] p;
}

// 快排分割处理函数
int Partition(int arr[], int l, int r)
{
	// 优化2：选择基准数的优化，“三数取中”，arr[l] arr[r]  arr[(l+r)/2]

	// 基类基准数
	int val = arr[l];
	// 一次快排处理 O(n)
	while (l < r)
	{
		while (l < r && arr[r] > val)  // 从右边开始往前找一个小于val的数字
		{
			r--;
		}
		if (l < r)
		{
			arr[l] = arr[r];
			l++;
		}

		while (l < r && arr[l] < val)  // 从左边开始找到大于val的数
		{
			l++;
		}
		if (l < r)
		{
			arr[r] = arr[l];
			r--;
		}
	}
	// 最后，当l == r时候，arr[r] = val
	arr[r] = val;
	return r;

}
// 时间复杂度：O(logn)   * O(n)
// 空间复杂度：递归占用的栈内存 O(logn)
// 最坏时间复杂度：n*O(n) = o(n^2)
void QuickSort(int arr[], int begin, int end)  // 1 递归的参数
{
	// 2 递归的结束条件 
	if (begin >= end)
	{
		return;
	}
	 优化1：当[begin,end]序列的元素个数小于指定数量时候，采用插入排序
	//if (end - begin <= N)  // 这个 N 根据实际的数量进行调试，确定。
	//{
	//	InsertSort1(arr, end - begin);
	//	return;
	//}
	// 3 在begin 和 end 之间做一次快排分割处理
	int pos = Partition(arr, begin, end);  // O(n)

	// 对基准数的左右序列，再分别进行快排。
	QuickSort(arr, begin, pos - 1);
	QuickSort(arr, pos + 1, end);
}

void QuickSort(int arr[], int size)
{
	QuickSort(arr, 0, size - 1);
}
// 堆的下沉调整 
void siftDown(int arr[], int i, int size)  //  i表示第i个非叶子节点
{
	int val = arr[i];		// 记录非叶子节点值
	while (i < size / 2)    // (size - 1 - 1 )/ 2 = size - 2 /2 = size/2-1
	{
		int child = 2 * i + 1;
		if (child + 1 < size && arr[child + 1] > arr[child])
		{
			child = child + 1;
		}

		if (arr[child] > val)   // 如果孩子值大于节点值
		{
			arr[i] = arr[child];
			i = child;
		}
		else
		{
			break;
		}
	}
	arr[i] = val; // 将非叶子节点放入i位置
}
// 堆排序
// 时间复杂度：O(logn) * O(n)
// 不稳定 

void HeapSort(int arr[], int size)
{
	int n = size - 1;

	// 1 从第一个非叶子节点开始进行大根堆调整
	for (int i = (n - 1) / 2; i >= 0; i--)
	{
		siftDown(arr, i, size);
	}
	// 2  把堆顶元素和末尾元素进行交换，从0号位置开始进行堆的下沉
	for (int i = n; i > 0; i--)
	{
		int tmp = arr[0];
		arr[0] = arr[i];
		arr[i] = tmp;

		siftDown(arr, 0, i);  // 第三个参数，表示参与调整个数，每次不同排序最后一个元素
	}
}


// 思想：
int main()
{
	const int COUNT = 8000000;
	int* arr = new int[COUNT];
	int* brr = new int[COUNT];
	int* crr = new int[COUNT];

	srand(time(NULL));

	for (int i = 0; i < COUNT; i++)
	{
		int val = rand() % COUNT;
		arr[i] = val;
		brr[i] = val;
		crr[i] = val;
	}

	cout << endl;

	clock_t begin, end;
	begin = clock();
	QuickSort(arr, COUNT);
	end = clock();
	cout << "QuickSort spend:" << (end - begin) * 1.0 / CLOCKS_PER_SEC << "s" << endl;


	begin = clock();
	MergeSort1(brr, COUNT);
	end = clock();
	cout << "MergeSort1 spend:" << (end - begin) * 1.0 / CLOCKS_PER_SEC << "s" << endl;

	begin = clock();
	HeapSort(crr, COUNT);
	end = clock();
	cout << "HeapSort spend:" << (end - begin) * 1.0 / CLOCKS_PER_SEC << "s" << endl;


	cout << endl;
	system("pause");
	return 0;
}

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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222