算法思想：每次生成一个样本用不同的排序测试并记录所用时间，一共十个样本，最后输出结果。
主要/核心函数分析：堆排序：将带排序的序列构造成一个大顶堆，根据大顶堆的性质，当前堆的根节点（堆顶）就是序列中最大的元素，将堆顶元素和最后一个元素交换，然后将剩下的节点重新构造成一个大顶堆。归并排序：将一个数组拆分为两个，从中间点拆开，通过递归操作来实现一层一层拆分，从左右数组中选择小的元素放入到临时空间，并移动下标到下一位置，重复前面步骤直到某一下标达到尾部，将另一序列剩下的所有元素依次放入临时空间，将临时空间的数据依次放入原数据数组。快速排序：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。基数排序：将所有待比较数值统一为同样的位数长度，数位较短的数前边补零。然后，从最低位开始，依次进行一次排序，这样从最低位排序一直到最高位排序完成后，就变成一个有序数列。选择排序：第一次从arr[0到]arr[n-1]中选取最小值，与arr[0]交换，第二次从arr[1]到arr[n-1]中选取最小值，与arr[1]交换，第三次从arr[2]到arr[n-1]中选取最小值，与arr[2]交换，…，第i次从arr[i-1]arr[n-1]中选取最小值，与arr[i-1]交换，…, 第n-1次从arr[n-2]~arr[n-1]中选取最小值，与arr[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。希尔排序：把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量主键递减，每组包含的关键词也来越多，当增量减至1时，整个文件恰被分成一组，算法终止。插入排序：构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
测试数据：系统随机生成的10个样本，每个样本有50000个随机整数
运行结果：
排序算法/时间
插入排序：922 859 875 875 875 890 859 860 859 875
希尔排序：15 0 0 0 15 16 16 15 0 0
冒泡排序：4703 4610 4625 4609 4594 4640 4625 4625 4672 4609
快速排序：0 0 15 0 0 0 0 0 0 0
选择排序：1360 1375 1375 1360 1375 1375 1375 1375 1390 1375
堆排序：15 0 0 15 16 16 0 16 0 16
归并排序：16 15 16 16 0 16 15 16 16 16
基数排序：0 0 0 0 15 0 16 0 0 0
时间复杂度：冒泡，插入排序：O（n*n）。希尔，希尔，快速，归并，堆排序：O（n*logn）。基数排序O（k*n）。
1 #include <iostream>
2 #include<fstream>
3 #include <time.h>
4 #include <stdio.h>
5 #include <assert.h>
6 #include <stdlib.h> /* srand, rand */
7 #include <vector>
8 #include <queue>
9 #include <Windows.h>
10
11 using namespace std;
12
13 int a1[50001];
14 int a2[50001];
15 int a3[50001];
16 int a4[50001];
17 int a5[50001];
18 int a6[50001];
19 int a7[50001];
20 int a8[50001];
21 int a[9][11];
22 const int val_count = 50000; //8seconds for selection, 0 seconds
23 int num = 0;
24
25 //冒泡排序
26 void bubblesort(int *a)
27 {
28 for (int i = 0; i < num - 1; i++)
29 {
30 for (int j = i + 1; j < num; j++)
31 {
32 if (a[i] > a[j])
33 {
34 int temp = a[i];
35 a[i] = a[j];
36 a[j] = temp;
37 }
38 }
39 }
40 }
41
42 //选择排序
43 void selectionsort(int *a)
44 {
45 for (int i = 0; i < num - 1; i++)
46 {
47 int key = i;
48 for (int j = i + 1; j < num; j++)
49 {
50 if (a[j] < a[key])
51 key = j;
52 }
53 int temp = a[i];
54 a[i] = a[key];
55 a[key] = temp;
56 }
57 }
58
59 //插入排序
60 void insertsort(int *a)
61 {
62 for (int i = 1; i < num; i++)
63 {
64 int tmp = a[i];
65 int j = 0;
66 for (j = i - 1; j >= 0; j--)
67 {
68 if (a[j] > tmp)
69 a[j + 1] = a[j];
70 else
71 break;
72 }
73 a[j + 1] = tmp;
74 }
75 }
76
77 void shellfunction(int *a,int gap)
78 {
79 for (int i = gap; i < num; i++)
80 {
81 int tmp = a[i];
82 int j = 0;
83 for (j = i - gap; j >= 0; j = j - gap)
84 {
85 if (a[j] > tmp)
86 a[j + gap] = a[j];
87 else
88 break;
89 }
90 a[j + gap] = tmp;
91 }
92 }
93
94 //希尔排序
95 void shellsort(int *a)
96 {
97 int gap = num;//间隔
98 while (gap > 1)
99 {
100 gap = gap / 2;
101 shellfunction(a,gap);
102 }
103 }
104
105 //归并排序
106 void mergesort(int* a,int left,int right)
107 {
108 if (a==NULL||left >= right)
109 return;
110 int mid = (left + right) / 2;
111 mergesort(a, left, mid);
112 mergesort(a, mid + 1, right);
113
114 int* tmp = (int*)malloc((right - left + 1) * sizeof(int));
115 // tmp是汇总2个有序区间的临时区域。
116 int i = left; // 第一个有序区的索引
117 int j = mid + 1; // 第二个有序区的索引
118 int k = 0; // 临时区域的索引
119 while (i <= mid && j <= right)
120 {
121 if (a[i] <= a[j])
122 tmp[k++] = a[i++];
123 else
124 tmp[k++] = a[j++];
125 }
126 while (i <= mid)
127 tmp[k++] = a[i++];
128
129 while (j <= right)
130 tmp[k++] = a[j++]; // 将两个有序区间合并
131
132 // 排序后的元素，全部都整合到数组a中
133 for (i = 0; i < k; i++)
134 a[left + i] = tmp[i];
135 }
136
137 void maxheap_sort(int* a, int start, int end)
138 {
139 int c = start; // 当前（current）节点的位置
140 int l = 2 * c + 1; // 左（left）孩子的位置
141 int tmp = a[c]; // 当前（current）节点的大小
142 for (; l <= end; c = l, l = 2 * l + 1)
143 {
144 // “l”是左孩子，“l+1”是右孩子
145 if (l < end && a[l] < a[l + 1])
146 l++; // 左右两个孩子中选择较大者，即m_heap[l+1]
147 if (tmp >= a[l])
148 break; // 调整结束d
149 else
150 {// 交换值
151 a[c] = a[l];
152 a[l] = tmp;
153 }
154 }
155 }
156
157 //堆排序
158 void heapsort(int* a)
159 {
160 int i;
161 // 从（n/2-1）--> 0 逐次遍历。遍历之后，得到的数组实际上是一个（最大）二叉堆
162 for (i = num / 2 - 1; i >= 0; i--) {
163 maxheap_sort(a, i, num - 1);
164 }
165 // 从最后一个元素开始对序列进行调整，不断地缩小调整的范围直到第一个元素
166 for (i = num - 1; i > 0; i--) {
167 // 交换a[0]和a[i]。交换后，a[i]是a[0..i]中最大的。
168 int temp = a[0];
169 a[0] = a[i];
170 a[i] = temp;
171 // 调整a[0..i-1]，使得a[0..i-1]仍然是一个最大堆。
172 // 即，保证a[i-1]是a[0..i-1]中的最大值。
173 maxheap_sort(a, 0, i - 1);
174 }
175 }
176
177 //快速排序
178 void quicksort(int *a,int start,int end)
179 {
180 if (start > end)
181 return;
182
183 int i = start;
184 int j = end;
185 int pirot = a[i];
186 while (i < j)
187 {
188 while (i<j && a[j]>pirot)
189 j--;
190 while (i < j && a[i] <= pirot)
191 i++;
192 if (i < j)
193 {
194 int tmp = a[i];
195 a[i] = a[j];
196 a[j] = tmp;
197 }
198 }
199 a[start] = a[i];
200 a[i] = pirot;
201 quicksort(a,start, i-1);
202 quicksort(a,i + 1, end);
203 }
204
205 //基数排序
206 void radixsort(int* a)
207 {
208 //max为数组中最大值
209 int max = a[0];
210 int base = 1;
211
212 //找出数组中的最大值
213 for (int i = 0; i < num; i++)
214 if (a[i] > max)
215 max = a[i];
216 //循环结束max就是数组最大值
217
218 //临时存放数组元素的空间
219 int* tmp = (int*)malloc(sizeof(int) * num);
220
221 //循环次数为最大数的位数
222 while (max / base > 0)
223 {
224 //定义十个桶，桶里面装的不是数据本身，而是每一轮排序对应（十、白、千...）位的个数
225 //统计每个桶里面装几个数
226 int bucket[10] = { 0 };
227 for (int i = 0; i < num; i++)
228 //arr[i] / base % 10可以取到个位、十位、百位对应的数字
229 bucket[a[i] / base % 10]++;
230 //循环结束就已经统计好了本轮每个桶里面应该装几个数
231
232 //将桶里面的元素依次累加起来，就可以知道元素存放在临时数组中的位置
233 for (int i = 1; i < 10; i++)
234 bucket[i] += bucket[i - 1];
235 //循环结束现在桶中就存放的是每个元素应该存放到临时数组的位置
236
237 //开始放数到临时数组tmp
238 for (int i = num - 1; i >= 0; i--)
239 {
240 tmp[bucket[a[i] / base % 10] - 1] = a[i];
241 bucket[a[i] / base % 10]--;
242 }
243 //不能从前往后放，因为这样会导致十位排好了个位又乱了，百位排好了十位又乱了
244 /*for (int i = 0; i < n; i++)
245 {
246 tmp[bucket[arr[i] / base % 10] - 1] = arr[i];
247 bucket[arr[i] / base % 10]--;
248 }*/
249
250 //把临时数组里面的数拷贝回去
251 for (int i = 0; i < num; i++)
252 a[i] = tmp[i];
253 base *= 10;
254 }
255 free(tmp);
256 }
257
258 void print(int* a)
259 {
260 cout << "数组是:" << endl;
261 for (int i = 0; i < num; i++)
262 cout << a[i] << " ";
263 cout << endl;
264 }
265
266 void test(int i)
267 {
268 srand(time(NULL));
269 fstream file;
270 file.open("big-a.txt", ios::out);
271 for (int i = 0; i < val_count - 1; i++) {
272 int val = (rand() % 5000000);
273 file << val << endl;
274 }
275 int val = (rand() % 5000000);
276 file << val;
277 file.close();
278
279 //样本2
280 num = 0;
281 fstream fp;
282 fp.open("big-a.txt", ios::in);
283 while (!fp.eof())
284 {
285 fp >> a1[num];
286 a2[num] = a1[num];
287 a3[num] = a1[num];
288 a4[num] = a1[num];
289 a5[num] = a1[num];
290 a6[num] = a1[num];
291 a7[num] = a1[num];
292 a8[num] = a1[num];
293 num++;
294 }
295 fp.close();
296
297 DWORD start, end;
298 start = GetTickCount();
299 insertsort(a1);
300 end = GetTickCount();
301 a[1][i] = end - start;
302
303 start = GetTickCount();
304 shellsort(a2);
305 end = GetTickCount();
306 a[2][i] = end - start;
307
308 start = GetTickCount();
309 bubblesort(a3);
310 end = GetTickCount();
311 a[3][i] = end - start;
312
313 start = GetTickCount();
314 quicksort(a4, 0, num - 1);
315 end = GetTickCount();
316 a[4][i] = end - start;
317
318 start = GetTickCount();
319 selectionsort(a5);
320 end = GetTickCount();
321 a[5][i] = end - start;
322
323 start = GetTickCount();
324 heapsort(a6);
325 end = GetTickCount();
326 a[6][i] = end - start;
327
328 start = GetTickCount();
329 mergesort(a7, 0, num - 1);
330 end = GetTickCount();
331 a[7][i] = end - start;
332
333 start = GetTickCount();
334 radixsort(a8);
335 end = GetTickCount();
336 a[8][i] = end - start;
337 }
338
339 int main()
340 {
341 test(1);
342 test(2);
343 test(3);
344 test(4);
345 test(5);
346 test(6);
347 test(7);
348 test(8);
349 test(9);
350 test(10);
351
352 //测试
353 //print(a1); print(a2); print(a3); print(a4); print(a5); print(a6); print(a7); print(a8);
354
355 cout << "排序算法/时间" << endl;
356
357 cout << "插入排序：";
358 for (int i = 1; i <= 10; i++)
359 cout << a[1][i] << " ";
360 cout << endl;
361
362 cout << "希尔排序：";
363 for (int i = 1; i <= 10; i++)
364 cout << a[2][i] << " ";
365 cout << endl;
366
367 cout << "冒泡排序：";
368 for (int i = 1; i <= 10; i++)
369 cout << a[3][i] << " ";
370 cout << endl;
371
372 cout << "快速排序：";
373 for (int i = 1; i <= 10; i++)
374 cout << a[4][i] << " ";
375 cout << endl;
376
377 cout << "选择排序：";
378 for (int i = 1; i <= 10; i++)
379 cout << a[5][i] << " ";
380 cout << endl;
381
382 cout << " 堆排序：";
383 for (int i = 1; i <= 10; i++)
384 cout << a[6][i] << " ";
385 cout << endl;
386
387 cout << "归并排序：";
388 for (int i = 1; i <= 10; i++)
389 cout << a[7][i] << " ";
390 cout << endl;
391
392 cout << "基数排序：";
393 for (int i = 1; i <= 10; i++)
394 cout << a[8][i] << " ";
395 cout << endl;
396
397 return 0;
398 }
标签：arr,end,int,start,num,八大,排序 From： https://www.cnblogs.com/saucerdish/p/17930134.html