10种排序算法代码+综合比较代码（直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、基数排序、折半插入...

#include<iostream> #include<ctime> #include<math.h> #define N 100001 using namespace std; long long sum[5][10][3]; int randNum[N]; int randNum1[N - 1]; //显示数组 void show(int randNum[N]) { for (int i = 1; i < N; i++) printf("%6d", randNum[i]); cout << endl; } //产生随机数 void proRandNum(int *randNum) { randNum[0] = 0; srand((unsigned)clock()); for (int i = 1; i < N; i++) randNum[i] = rand(); } //产生正序 void proPosiNum(int *posiNum) { posiNum[0] = 0; for (int i = 1; i < N; i++) posiNum[i] = i; } //产生逆序 void proNegaNum(int *negaNum) { negaNum[0] = 0; for (int i = 1; i < N; i++) negaNum[i] = N- i; } //前一半有序，后一半随机 void proPosiRandNum(int *posiRand) { posiRand[0] = 0; for (int i = 1; i < N / 2 + 1; i++) posiRand[i] = i; srand((unsigned)time(NULL)); for (int i = N / 2 + 1; i < N; i++) posiRand[i] = rand(); } //前一半随机，后一半有序 void proRandPosiNum(int *randPosi) { randPosi[0] = 0; srand((unsigned)time(NULL)); for (int i = 1; i < N / 2 + 1; i++) randPosi[i] = rand(); for (int i = N / 2 + 1; i < N; i++) randPosi[i] = i; } //输入结果 void resultPrint(int num, int num2) { cout << " 比较次数 移动次数 运行时间（ms）\n"; switch (num2) { case 0: if (num + 1 == 11) { for (int i = 0; i < 10; i++) { switch (i + 1) { case 1:cout << "直接插入排序："; break; case 2:cout << " 希尔排序 ："; break; case 3:cout << " 冒泡排序 ："; break; case 4:cout << " 快速排序 ："; break; case 5:cout << "简单选择排序："; break; case 6:cout << " 堆排序 ："; break; case 7:cout << " 归并排序 ："; break; case 8:cout << " 基数排序 ："; break; case 9:cout << "折半插入排序："; break; case 10:cout << "2路插入排序："; break; default: break; } printf("%12lld", (sum[0][i][0] + sum[1][i][0] + sum[2][i][0] + sum[3][i][0] + sum[4][i][0]) / 5); printf("%12lld", (sum[0][i][1] + sum[1][i][1] + sum[2][i][1] + sum[3][i][1] + sum[4][i][1]) / 5); printf("%12lld", (sum[0][i][2] + sum[1][i][2] + sum[2][i][2] + sum[3][i][2] + sum[4][i][2]) / 5); cout << endl; } break; } for (int i = 0; i < 5; i++) { cout << "数据" << i + 1 << "： "; printf("%12lld", sum[i][num][0]); printf("%12lld", sum[i][num][1]); printf("%12lld", sum[i][num][2]); cout << endl; } cout << "均值: "; printf("%12lld", (sum[0][num][0] + sum[1][num][0] + sum[2][num][0] + sum[3][num][0] + sum[4][num][0]) / 5); printf("%12lld", (sum[0][num][1] + sum[1][num][1] + sum[2][num][1] + sum[3][num][1] + sum[4][num][1]) / 5); printf("%12lld", (sum[0][num][2] + sum[1][num][2] + sum[2][num][2] + sum[3][num][2] + sum[4][num][2]) / 5); cout << endl; break; case 1: case 2: case 3: case 4: if (num + 1 == 11) { for (int i = 0; i < 10; i++) { switch (i + 1) { case 1:cout << "直接插入排序："; break; case 2:cout << " 希尔排序 ："; break; case 3:cout << " 冒泡排序 ："; break; case 4:cout << " 快速排序 ："; break; case 5:cout << "简单选择排序："; break; case 6:cout << " 堆排序 ："; break; case 7:cout << " 归并排序 ："; break; case 8:cout << " 基数排序 ："; break; case 9:cout << "折半插入排序："; break; case 10:cout << "2路插入排序："; break; default: break; } printf("%12lld", sum[4][i][0]); printf("%12lld", sum[4][i][1]); printf("%12lld", sum[4][i][2]); cout << endl; } break; } cout << "数据"<< "： "; printf("%12lld", sum[4][num][0]); printf("%12lld", sum[4][num][1]); printf("%12lld", sum[4][num][2]); cout << endl; break; } //清零 for (int i = 0; i < 5; i++) for (int j = 0; j < 10; j++) for (int k = 0; k < 3; k++) sum[i][j][k] = 0; } //1.直接插入排序 void straightInsertSort(int *randNum, int n) { int i, j; for (i = 2; i < N;++i) if (sum[n][0][0]++,randNum[i] < randNum[i - 1]) { randNum[0] = randNum[i]; randNum[i] = randNum[i - 1]; sum[n][0][1] += 2; for (j = i - 2; sum[n][0][0]++, randNum[0] < randNum[j]; --j) { randNum[j + 1] = randNum[j]; sum[n][0][1]++; } randNum[j + 1] = randNum[0]; sum[n][0][1]++; } } //2.希尔排序 void shellSort(int randNum[N], int n) { int dlta[17]; int j; for (int k = 0; k <= 16; k++) { dlta[k] = pow(2, 16 - k) + 1; } for (int k = 0; k <= 16; k++) { for (int i = dlta[k] + 1; i < N; i++) { if (sum[n][1][0]++, randNum[i] < randNum[i - dlta[k]]) { sum[n][1][1]++; randNum[0] = randNum[i]; for (j = i - dlta[k]; sum[n][1][0]++, j > 0 && randNum[0] < randNum[j]; j -= dlta[k]) { sum[n][1][1]++; randNum[j + dlta[k]] = randNum[j]; } sum[n][1][1]++; randNum[j + dlta[k]] = randNum[0]; } } } //show(randNum); } //3.冒泡排序 void bubbleSort(int randNum[N], int n) { int i, j; long long t; for (i = 1; i<N-1; i++) for (j = 1; j<N - i; j++) { if (sum[n][2][0]++, randNum[j]>randNum[j + 1]) { t = randNum[j]; randNum[j] = randNum[j + 1]; randNum[j + 1] = t; sum[n][2][1] += 3; } } //show(randNum); } //4.快速排序 //取待排序序列中low、mid、high三个位置上数据，选取他们中间的那个数据作为枢轴 int SelectPivotMedianOfThree(int arr[], int low, int high) { int mid = low + (high - low) / 2; if (arr[mid] > arr[high]) swap(arr[mid], arr[high]); if (arr[low] > arr[high]) swap(arr[low], arr[high]); if (arr[mid] > arr[low]) swap(arr[mid], arr[low]); return arr[low]; } int partition(int *randNum, int low, int high, int n) { randNum[0] = randNum[low]; int pivotkey = SelectPivotMedianOfThree(randNum, low, high); while (low < high) { while (low < high&&randNum[high] >= pivotkey) { --high; sum[n][3][0]++; } randNum[low] = randNum[high]; sum[n][3][1]++; while (low < high&&randNum[low] <= pivotkey) { ++low; sum[n][3][0]++; } randNum[high] = randNum[low]; sum[n][3][1]++; } randNum[low] = randNum[0]; return low; } void QSort(int *randNum, int low, int high, int n) { if (low < high) { int pivotloc = partition(randNum, low, high, n); if (pivotloc - 1 - low <= high - pivotloc - 1) { if(pivotloc!=low) QSort(randNum, low, pivotloc - 1, n); if(pivotloc != high) QSort(randNum, pivotloc + 1, high, n); } else { if (pivotloc != high) QSort(randNum, pivotloc + 1, high, n); if (pivotloc != low) QSort(randNum, low, pivotloc - 1, n); } } } void quickSort(int *randNum, int n) { QSort(randNum, 1, N - 1, n); //show(randNum); } //5.简单选择排序 void simpleSelectionSort(int randNum[N], int n) { int i, j, min, ex; for (i = 1; i < N-1; i++) { min = i; for (j = i+1; j < N; j++) { if (sum[n][4][0]++, randNum[min] > randNum[j]) min = j; } if (min != i) { ex = randNum[i]; randNum[i] = randNum[min]; randNum[min] = ex; sum[n][4][1] += 3; } } //show(randNum); } //6.堆排序 void heapAdjust(int *randNum, int s, int m, int n) { int rc = randNum[s]; for (int j = 2 * s; j <= m; j *= 2) { if (sum[n][5][0]++, j < m&&randNum[j] < randNum[j + 1]) ++j; if (rc >= randNum[j]) break; randNum[s] = randNum[j]; s = j; sum[n][5][1]++; } randNum[s] = rc; sum[n][5][1]++; } void heapSort(int *randNum, int n) { int i,ex; for (i = (N - 1) / 2; i > 0; --i) heapAdjust(randNum, i, N - 1, n); for (i = N - 1; i > 1; --i) { swap(randNum[i], randNum[1]); heapAdjust(randNum, 1, i - 1, n); } //show(randNum); } //7.归并排序 void mergingSort(int *randNum, int n) { //MSort(randNum, randNum, 1, N - 1, n); int i, left_min, left_max, right_min, right_max, next; int *tmp = (int*)malloc(sizeof(int) * (N-1)); if (tmp == NULL) { fputs("Error: out of memory\n", stderr); abort(); } for (i = 1; i < N-1; i *= 2) // i为步长，1,2,4,8…… { for (left_min = 1; left_m