算法思想：每次生成一个样本用不同的排序测试并记录所用时间，一共十个样本，最后输出结果。
主要/核心函数分析：堆排序：将带排序的序列构造成一个大顶堆，根据大顶堆的性质，当前堆的根节点（堆顶）就是序列中最大的元素，将堆顶元素和最后一个元素交换，然后将剩下的节点重新构造成一个大顶堆。归并排序：将一个数组拆分为两个，从中间点拆开，通过递归操作来实现一层一层拆分，从左右数组中选择小的元素放入到临时空间，并移动下标到下一位置，重复前面步骤直到某一下标达到尾部，将另一序列剩下的所有元素依次放入临时空间，将临时空间的数据依次放入原数据数组。快速排序：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。基数排序：将所有待比较数值统一为同样的位数长度，数位较短的数前边补零。然后，从最低位开始，依次进行一次排序，这样从最低位排序一直到最高位排序完成后，就变成一个有序数列。选择排序：第一次从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 }