这一节,测试各类排序算法的运行速度(没有基数排序(桶)
其实在实际学习中,还是有意义的
给定 n 个(长整型范围内的)整数,要求输出从小到大排序后的结果。
本题旨在测试各种不同的排序算法在各种数据情况下的表现。各组测试数据特点如下:
- 数据1:只有1个元素;
- 数据2:11个不相同的整数,测试基本正确性;
- 数据3:个随机整数;
- 数据4:个随机整数;
- 数据5:个随机整数;
- 数据6:个顺序整数;
- 数据7:个逆序整数;
- 数据8:个基本有序的整数;
- 数据9:个随机正整数,每个数字不超过1000。
输入格式:
输入第一行给出正整数 n(≤105),随后一行给出 n 个(长整型范围内的)整数,其间以空格分隔。
输出格式:
在一行中输出从小到大排序后的结果,数字间以 1 个空格分隔,行末不得有多余空格。
输入样例:
11 4 981 10 -17 0 -20 29 50 8 43 -5
输出样例:
-20 -17 -5 0 4 8 10 29 43 50 981
//冒泡排序
//冒泡排序 void Bubble_Sort(int *a, int Num) {int Temp, i, j;int flag;for(i = 0; i < Num; i++){flag = 0;for(j = 0; j < Num - 1; j++){if(a[j] > a[j + 1]){Temp = a[j];a[j] = a[j+1];a[j+1] = Temp;flag = 1;}}if(!flag){break;}} }
测试点 提示 内存(KB) 用时(ms) 结果 得分 0 352 2 答案正确
1 / 1 1 332 2 答案正确
10 / 10 2 356 3 答案正确
2 / 2 3 276 192 答案正确
2 / 2 4 688 3000 运行超时
0 / 2 5 1200 17 答案正确
2 / 2 6 664 3000 运行超时
0 / 2 7 1296 432 答案正确
2 / 2 8 668 3000 运行超时
0 / 2
插入排序
void Insert_Sort(int *a, int Num) {int i, j;int Temp;for(i = 1; i < Num; i++){Temp = a[i];for(j = i; j > 0 && a[j-1] > Temp; j--){a[j] = a[j-1];}a[j] = Temp;} }
测试点 提示 内存(KB) 用时(ms) 结果 得分 0 360 1 答案正确
1 / 1 1 176 1 答案正确
10 / 10 2 356 2 答案正确
2 / 2 3 424 16 答案正确
2 / 2 4 1144 1254 答案正确
2 / 2 5 1200 17 答案正确
2 / 2 6 1176 2493 答案正确
2 / 2 7 1208 29 答案正确
2 / 2 8 1048 1260 答案正确
2 / 2
希尔排序_普通版
void Shell_Sort(int *a, int Num) {int D, P, i;int Temp;for(D = Num / 2; D > 0; D /= 2){for(P = D; P < Num; P++){Temp = a[P];for(i = P; i >= D && a[i - D] > Temp; i -= D){a[i] = a[i - D];}a[i] = Temp;}} }
测试点 提示 内存(KB) 用时(ms) 结果 得分 0 176 2 答案正确
1 / 1 1 308 2 答案正确
10 / 10 2 336 2 答案正确
2 / 2 3 412 4 答案正确
2 / 2 4 1132 30 答案正确
2 / 2 5 1144 21 答案正确
2 / 2 6 1332 22 答案正确
2 / 2 7 1204 22 答案正确
2 / 2 8 1076 27 答案正确
2 / 2
希尔排序_Hibbard版,就是将增量换成,由2^i 到 2^i-1;达到相邻元素互质,保证有效间隔。
Tworst= O( N^3/2) , Tavg = O ( N^5/4);
void Shell_Sort_Hibbard(int *a, int Num) {int H, D, P, i;int Temp;int Hibbard[] = {131071, 65535, 32767, 16383, 8191, 4095, 2047, 1023, 511, 255, 127, 63, 31, 15, 7, 3, 1};for(H = 0; Hibbard[H] >= Num; H++);for(D = Hibbard[H]; D > 0; D = Hibbard[++H]){for(P = D; P < Num; P++){Temp = a[P];for(i = P; i >= D && a[i - D] > Temp; i -= D){a[i] = a[i - D];}a[i] = Temp;}} }/* num1[0] == 0 num1[1] == 1 num1[2] == 3 num1[3] == 7 num1[4] == 15 num1[5] == 31 num1[6] == 63 num1[7] == 127 num1[8] == 255 num1[9] == 511 num1[10] == 1023 num1[11] == 2047 num1[12] == 4095 num1[13] == 8191 num1[14] == 16383 num1[15] == 32767 num1[16] == 65535 num1[17] == 131071 num1[18] == 262143 num1[19] == 524287*/
测试点 提示 内存(KB) 用时(ms) 结果 得分 0 172 1 答案正确
1 / 1 1 316 1 答案正确
10 / 10 2 180 2 答案正确
2 / 2 3 440 4 答案正确
2 / 2 4 1152 30 答案正确
2 / 2 5 1200 20 答案正确
2 / 2 6 1180 20 答案正确
2 / 2 7 1148 20 答案正确
2 / 2 8 1048 27 答案正确
2 / 2
希尔排序_Sedgewick版,这个增量很厉害,9 * 4^i - 9 * 2^i + 1,或 4^i -3 *2^i +1;
Tavg = O ( N^7/6 ),Tworst = O ( N^4/3)
void Shell_Sort_Sedgewick(int *a, int Num) {int Si, D, P, i;int Temp;int Sedgewick[] = {146305, 64769, 36289, 16001, 8929, 3905, 2161, 929, 505, 209, 109, 41, 19, 5, 1, 0};for(Si = 0; Sedgewick[Si] >= Num; Si++);for(D = Sedgewick[Si]; D > 0; D = Sedgewick[++Si]){for(P = D; P < Num; P++){Temp = a[P];for(i = P; i >= D && a[i - D] > Temp; i -= D){a[i] = a[i - D];}a[i] = Temp;}} }//有同学问,这一序列如何来的,其实是综合两个函数 // 具体的数学逻辑我也不懂 #include <stdio.h> #include <math.h>int main() {int i;double num1;double num2;for(i = 0; i < 10; i++){num1 = 9.0 * pow(4, i) - 9.0 * pow(2, i) + 1;printf("num1[%d] == %.lf\n", i, num1);}for(i = 0; i < 10; i++){num2 = pow(4, i) - 3.0 * pow(2, i) + 1;printf("num2[%d] == %.lf\n", i, num2);} return 0; } /* 这是运行结果: num1[0] == 1 num1[1] == 19 num1[2] == 109 num1[3] == 505 num1[4] == 2161 num1[5] == 8929 num1[6] == 36289 num1[7] == 146305 num1[8] == 587521 num1[9] == 2354689 num2[0] == -1 num2[1] == -1 num2[2] == 5 num2[3] == 41 num2[4] == 209 num2[5] == 929 num2[6] == 3905 num2[7] == 16001 num2[8] == 64769 num2[9] == 260609 很明显,Sedgewick函数便是如此构成的, */
测试点 提示 内存(KB) 用时(ms) 结果 得分 0 172 2 答案正确
1 / 1 1 304 1 答案正确
10 / 10 2 360 2 答案正确
2 / 2 3 432 4 答案正确
2 / 2 4 1196 28 答案正确
2 / 2 5 1240 20 答案正确
2 / 2 6 1148 20 答案正确
2 / 2 7 1200 20 答案正确
2 / 2 8 1072 25 答案正确
2 / 2
#include<stdio.h>
#include<stdlib.h>void Bubble_Sort(int *a, int Num); //冒泡排序
void Insert_Sort(int *a, int Num); //插入排序
void Shell_Sort(int *a, int Num); //希尔排序
void Shell_Sort_Hibbard(int *a, int Num); //希尔排序
void Shell_Sort_Sedgewick(int *a, int Num); //希尔排序
//void Selection_Sort(int *a, int Num);// 选择排序
//void Heap_Sort(); //堆排序
//void Merge_Sort(); //归并排序
//void Quick_Sort(); //快速排序
//void Table_Sort(); //表排序
//void Radix_Sort(); //基数排序, 桶排序int main()
{int Num, i;int *a;scanf("%d", &Num);a = (int *)malloc(sizeof(int) * Num);for(i = 0; i < Num; i++){scanf("%d", &a[i]);}
// Bubble_Sort(a, Num);
// Insert_Sort(a, Num);
// Shell_Sort(a, Num);
// Shell_Sort_Hibbard(a, Num);
// Shell_Sort_Sedgewick(a, Num);Selection_Sort(a, Num);for(i = 0; i < Num - 1; i++){printf("%d ", a[i]);}printf("%d\n", a[i]);return 0;
}void Bubble_Sort(int *a, int Num)
{int Temp, i, j;int flag;for(i = 0; i < Num; i++){flag = 0;for(j = 0; j < Num - 1; j++){if(a[j] > a[j + 1]){Temp = a[j];a[j] = a[j+1];a[j+1] = Temp;flag = 1;}}if(!flag){break;}}
}
void Insert_Sort(int *a, int Num)
{int i, j;int Temp;for(i = 1; i < Num; i++){Temp = a[i];for(j = i; j > 0 && a[j-1] > Temp; j--){a[j] = a[j-1];}a[j] = Temp;}
}void Shell_Sort(int *a, int Num)
{int D, P, i;int Temp;for(D = Num / 2; D > 0; D /= 2){for(P = D; P < Num; P++){Temp = a[P];for(i = P; i >= D && a[i - D] > Temp; i -= D){a[i] = a[i - D];}a[i] = Temp;}}
}
void Shell_Sort_Hibbard(int *a, int Num)
{int H, D, P, i;int Temp;int Hibbard[] = {131071, 65535, 32767, 16383, 8191, 4095, 2047, 1023, 511, 255, 127, 63, 31, 15, 7, 3, 1};for(H = 0; Hibbard[H] >= Num; H++);for(D = Hibbard[H]; D > 0; D = Hibbard[++H]){for(P = D; P < Num; P++){Temp = a[P];for(i = P; i >= D && a[i - D] > Temp; i -= D){a[i] = a[i - D];}a[i] = Temp;}}
}void Shell_Sort_Sedgewick(int *a, int Num)
{int Si, D, P, i;int Temp;int Sedgewick[] = {146305, 64769, 36289, 16001, 8929, 3905, 2161, 929, 505, 209, 109, 41, 19, 5, 1, 0};for(Si = 0; Sedgewick[Si] >= Num; Si++);for(D = Sedgewick[Si]; D > 0; D = Sedgewick[++Si]){for(P = D; P < Num; P++){Temp = a[P];for(i = P; i >= D && a[i - D] > Temp; i -= D){a[i] = a[i - D];}a[i] = Temp;}}
}
void Selection_Sort(int *a, int Num)
{int i,k, Min;int Temp, MinValue;for(k = 0; k < Num; k++){MinValue = 21000000;for(i = k; i < Num; i++){if(a[i] < MinValue){MinValue = a[i];Min = i;}}Temp = a[k];a[k] = a[Min];a[Min] = Temp;}
}
选择排序,依旧稳定发挥void Selection_Sort(int *a, int Num) {int i,k, Min;int Temp, MinValue;for(k = 0; k < Num; k++){MinValue = 21000000;for(i = k; i < Num; i++){if(a[i] < MinValue){MinValue = a[i];Min = i;}}Temp = a[k];a[k] = a[Min];a[Min] = Temp;} }
测试点 提示 内存(KB) 用时(ms) 结果 得分 0 304 1 答案正确
1 / 1 1 304 1 答案正确
10 / 10 2 308 2 答案正确
2 / 2 3 320 55 答案正确
2 / 2 4 632 3000 运行超时
0 / 2 5 608 3000 运行超时
0 / 2 6 560 3000 运行超时
0 / 2 7 696 3000 运行超时
0 / 2 8 552 3000 运行超时
0 / 2
堆排序_简单版
测试点 提示 内存(KB) 用时(ms) 结果 得分 0 只有一个元素 180 3000 运行超时
0 / 1 1 172 1 答案正确
10 / 10 2 356 2 答案正确
2 / 2 3 432 4 答案正确
2 / 2 4 1180 27 答案正确
2 / 2 5 1264 23 答案正确
2 / 2 6 1204 23 答案正确
2 / 2 7 1220 22 答案正确
2 / 2 8 1020 26 答案正确
2 / 2 #include<stdio.h> #include<stdlib.h> #include<stdbool.h>typedef struct Heap *MinHeap; struct Heap{int *data;int Size; }; void Selection_Sort(int *a, int Num);// 选择排序 void Heap_Sort_Easy(int *a, int Num); //堆排序 void Swap(int *a, int *b); MinHeap Creat_Heap(int *a, int N); MinHeap Init_Heap(int N); void Insert_Heap(MinHeap H, int data); int Delete_Heap(MinHeap H); bool IsEmpty(MinHeap H);int main() {int Num, i;int *a;scanf("%d", &Num);a = (int *)malloc(sizeof(int) * Num);for(i = 0; i < Num; i++){scanf("%d", &a[i]);} // Selection_Sort(a, Num);Heap_Sort_Easy(a, Num);for(i = 0; i < Num - 1; i++){printf("%d ", a[i]);}printf("%d\n", a[i]);free(a);return 0; }void Selection_Sort(int *a, int Num) {int i,k, Min;int Temp, MinValue;for(k = 0; k < Num; k++){MinValue = 21000000;for(i = k; i < Num; i++){if(a[i] < MinValue){MinValue = a[i];Min = i;}}Swap(&a[k], &a[Min]);} } void Heap_Sort_Easy(int *a, int Num) {MinHeap H; // if(Num == 1){ // return ; // }H = Creat_Heap(a, Num);for(int i = 0; i < Num; i++){a[i] = Delete_Heap(H);}free(H ->data);free(H); } void Swap(int *a, int *b) {int Temp;Temp = *a;*a = *b;*b = Temp; } MinHeap Creat_Heap(int *a, int N) {MinHeap H;H = Init_Heap(N);for(int i = 0; i < N; i++){Insert_Heap(H, a[i]);}return H; } MinHeap Init_Heap(int N) {MinHeap H;H = (MinHeap)malloc(sizeof(struct Heap));H ->data = (int*)malloc(sizeof(int) * (N + 1));H ->data[0] = -2100000;H ->Size = 0;return H; } void Insert_Heap(MinHeap H, int data) {int i;i = ++H ->Size;for(; data < H ->data[i/2]; i /=2){H ->data[i] = H ->data[i/2];}H ->data[i] = data; } int Delete_Heap(MinHeap H) {int Parent, Child, i;int Min, Temp;if(IsEmpty(H)){printf("Is error!\n");return H ->data[0];}Min = H ->data[1];Temp = H ->data[H ->Size --];for(Parent = 1; Parent * 2 <= H ->Size; Parent = Child){Child = Parent * 2;if(H ->data[Child] > H ->data[Child + 1]){Child++;}if(Temp <= H ->data[Child]){break;}else{H ->data[Parent] = H ->data[Child];}}H ->data[Parent] = Temp;return Min; } bool IsEmpty(MinHeap H) {return (H ->Size == 0); }
堆排序_进阶版
测试点 提示 内存(KB) 用时(ms) 结果 得分 0 168 2 答案正确
1 / 1 1 304 1 答案正确
10 / 10 2 368 2 答案正确
2 / 2 3 432 4 答案正确
2 / 2 4 1188 28 答案正确
2 / 2 5 1272 23 答案正确
2 / 2 6 1276 23 答案正确
2 / 2 7 1152 22 答案正确
2 / 2 8 944 26 答案正确
2 / 2 #include<stdio.h> #include<stdlib.h>void Heap_Sort_Good(int *a, int Num); //堆排序 void Swap(int *a, int *b); void PercDown(int *a, int index, int Num);int main() {int Num, i;int *a;scanf("%d", &Num);a = (int *)malloc(sizeof(int) * Num);for(i = 0; i < Num; i++){scanf("%d", &a[i]);}Heap_Sort_Good(a, Num);for(i = 0; i < Num - 1; i++){printf("%d ", a[i]);}printf("%d\n", a[i]);return 0; }void Heap_Sort_Good(int *a, int Num) {int i, j;for(i = Num / 2 - 1; i >= 0;i--){PercDown(a, i, Num);}for(i = Num - 1; i > 0; i--){Swap(&a[0], &a[i]);PercDown(a, 0, i);} } void PercDown(int *a, int index, int Num) {int Parent, Child;int Value;Value = a[index];for(Parent = index; (Parent * 2 + 1) < Num; Parent = Child){Child = Parent * 2 + 1;if((Child != Num - 1) && a[Child] < a[Child + 1]){Child++;}if(Value >= a[Child]){break;}else{a[Parent] = a[Child];}}a[Parent] = Value; }void Swap(int *a, int *b) {int Temp;Temp = *a;*a = *b;*b = Temp; }
归并排序递归版
测试点 提示 内存(KB) 用时(ms) 结果 得分 0 364 2 答案正确
1 / 1 1 336 2 答案正确
10 / 10 2 368 2 答案正确
2 / 2 3 464 5 答案正确
2 / 2 4 1176 28 答案正确
2 / 2 5 1292 21 答案正确
2 / 2 6 1184 24 答案正确
2 / 2 7 1264 21 答案正确
2 / 2 8 1064 25 答案正确
2 / 2 #include<stdio.h> #include<stdlib.h>//归并排序 void Merge_Sort(int *a, int Num); void Msort(int *a, int *t, int LeftStart, int RightEnd); void Merge(int *a, int *t, int LeftStart, int RightStart, int RightEnd);int main() {int Num, i;int *a;scanf("%d", &Num);a = (int *)malloc(sizeof(int) * Num);for(i = 0; i < Num; i++){scanf("%d", &a[i]);}Merge_Sort(a, Num);for(i = 0; i < Num - 1; i++){printf("%d ", a[i]);}printf("%d\n", a[i]);return 0; }void Merge_Sort(int *a, int Num) {int *t;t = (int *)malloc(sizeof(int) * Num);if(t != NULL){Msort(a, t, 0, Num - 1);free(t);} } void Msort(int *a, int *t, int LeftStart, int RightEnd) {int center;if(LeftStart < RightEnd){center = ((LeftStart + RightEnd) / 2);Msort(a, t, LeftStart, center);Msort(a, t, center + 1, RightEnd);Merge(a, t, LeftStart, center + 1, RightEnd);} } void Merge(int *a, int *t, int LeftStart, int RightStart, int RightEnd) {int LeftEnd, Nums;int Temp;LeftEnd = RightStart - 1;Temp = LeftStart;Nums = RightEnd - LeftStart + 1;while((LeftStart <= LeftEnd) && (RightStart <= RightEnd)){if(a[LeftStart] <= a[RightStart]){t[Temp++] = a[LeftStart++];}else{t[Temp++] = a[RightStart++];}}while(LeftStart <= LeftEnd){t[Temp++] = a[LeftStart++];}while(RightStart <= RightEnd){t[Temp++] = a[RightStart++];}for(int i = 0; i < Nums; i++, RightEnd--){a[RightEnd] = t[RightEnd];} }
归并排序-非递归版
测试点 提示 内存(KB) 用时(ms) 结果 得分 0 176 2 答案正确
1 / 1 1 180 2 答案正确
10 / 10 2 356 2 答案正确
2 / 2 3 432 5 答案正确
2 / 2 4 1300 26 答案正确
2 / 2 5 1296 20 答案正确
2 / 2 6 1148 20 答案正确
2 / 2 7 1136 19 答案正确
2 / 2 8 1064 24 答案正确
2 / 2 #include<stdio.h> #include<stdlib.h>//归并排序 void Merge_Sort(int *a, int Num); void Msort(int *a, int *t, int Num, int Length); void Merge(int *a, int *t, int LeftStart, int RightStart, int RightEnd);int main() {int Num, i;int *a;scanf("%d", &Num);a = (int *)malloc(sizeof(int) * Num);for(i = 0; i < Num; i++){scanf("%d", &a[i]);}Merge_Sort(a, Num);for(i = 0; i < Num - 1; i++){printf("%d ", a[i]);}printf("%d\n", a[i]);return 0; }void Merge_Sort(int *a, int Num) {int *t;int Length = 1;t = (int *)malloc(sizeof(int) * Num);if(t != NULL){while(Length < Num){Msort(a, t, Num, Length);Length *= 2;Msort(t, a, Num, Length);Length *= 2;}free(t);} } void Msort(int *a, int *t, int Num, int Length) {int i, j;for(i = 0; i <= (Num - 2 * Length); i += 2 * Length){Merge(a, t, i, i + Length, (i + 2 * Length) - 1);}if(i + Length < Num){Merge(a, t, i, i + Length, Num - 1);}else{for(j = i; j < Num; j++){t[j] = a[j];}} } void Merge(int *a, int *t, int LeftStart, int RightStart, int RightEnd) {int LeftEnd, Nums;int Temp;LeftEnd = RightStart - 1;Temp = LeftStart;Nums = RightEnd - LeftStart + 1;while((LeftStart <= LeftEnd) && (RightStart <= RightEnd)){if(a[LeftStart] <= a[RightStart]){t[Temp++] = a[LeftStart++];}else{t[Temp++] = a[RightStart++];}}while(LeftStart <= LeftEnd){t[Temp++] = a[LeftStart++];}while(RightStart <= RightEnd){t[Temp++] = a[RightStart++];} }
快速排序_自定义版
测试点 提示 内存(KB) 用时(ms) 结果 得分 0 360 2 答案正确
1 / 1 1 356 2 答案正确
10 / 10 2 272 2 答案正确
2 / 2 3 344 5 答案正确
2 / 2 4 1144 31 答案正确
2 / 2 5 1208 18 答案正确
2 / 2 6 1292 19 答案正确
2 / 2 7 1204 19 答案正确
2 / 2 8 944 28 答案正确
2 / 2 #include<stdio.h> #include<stdlib.h>//归并排序void Swap(int *a, int *b); int Median3(int *a, int Left, int Right); void Qsort(int *a, int Left, int Right); void Quick_Sort(int *a, int Num); void Insert_Sort(int *a, int Num);int main() {int Num, i;int *a;scanf("%d", &Num);a = (int *)malloc(sizeof(int) * Num);for(i = 0; i < Num; i++){scanf("%d", &a[i]);}Quick_Sort(a, Num);for(i = 0; i < Num - 1; i++){printf("%d ", a[i]);}printf("%d\n", a[i]);return 0; } int Median3(int *a, int Left, int Right) {int Center = (Left + Right)/2;if(a[Left] > a[Center]){Swap(&a[Left], &a[Center]);}if(a[Left] > a[Right]){Swap(&a[Left], &a[Right]);}if(a[Center] > a[Right]){Swap(&a[Center], &a[Right]);}Swap(&a[Center], &a[Right - 1]);return a[Right - 1]; } void Qsort(int *a, int Left, int Right) {int Pivot, Cutoff, i, j; Cutoff = 1000;if(Cutoff < Right - Left){Pivot = Median3(a, Left, Right);i = Left; j = Right-1;while(1){while(a[++i] < Pivot);while(a[--j] > Pivot);if(i < j){Swap(&a[i], &a[j]);}else{break;}}Swap(&a[i], &a[Right - 1]);Qsort(a, Left, i - 1);Qsort(a, i + 1, Right);}else{Insert_Sort(a + Left, Right - Left + 1);} } void Quick_Sort(int *a, int Num) {Qsort(a, 0, Num - 1); } void Swap(int *a, int *b) {int Temp;Temp = *a;*a = *b;*b = Temp; } void Insert_Sort(int *a, int Num) {int i, j;int Temp;for(i = 1; i < Num; i++){Temp = a[i];for(j = i; j > 0 && a[j-1] > Temp; j--){a[j] = a[j-1];}a[j] = Temp;} }