首页 > 代码库 > 中国大学MOOC-数据结构基础习题集、07-1、排序
中国大学MOOC-数据结构基础习题集、07-1、排序
题目链接:http://www.patest.cn/contests/mooc-ds/07-1
题目分析:本题旨在测试各种不同的排序算法在各种数据情况下的表现。因此没有标准答案。本帖旨在给出各种排序算法的C++实现形式,并将结果进行比较、总结。希望能给大家带来帮助。
各种排序算法的代码:
1. 冒泡排序:
1 void Bubble_Sort(ElementType A[], int N) 2 { 3 for(int P=N-1; P>=0; P--) 4 { 5 int flag = 0; 6 for(int i=0; i<P; i++)/*一趟冒泡排序*/ 7 { 8 if(A[i] > A[i+1]) 9 {10 ElementType temp = A[i+1];11 A[i+1] = A[i];12 A[i] = temp;13 flag = 1;14 }15 }16 if(flag == 0) break;17 }18 }
2. 插入排序:
1 void Insertion_Sort(ElementType A[], int N) 2 { 3 for (int P=1; P<N; P++) 4 { 5 ElementType Tmp = A[P]; /* 摸一张牌 */ 6 int i; 7 for(i=P; i>0 && A[i-1]>Tmp; i--) 8 A[i] = A[i-1]; /* 移出空位 */ 9 A[i] = Tmp; /* 新牌落位 */10 }11 }
3. 希尔排序
1 void Shell_Sort(ElementType A[], int N) 2 { 3 for(int D=N/2; D>0; D/=2) /* 希尔增量序列 */ 4 { 5 for(int P=D; P<N; P++) 6 { 7 ElementType Tmp = A[P]; 8 int i; 9 for(i=P; i>=D && A[i-D]>Tmp; i-=D)10 A[i] = A[i-D];11 A[i] = Tmp;12 }13 }14 }
4. 选择排序
1 void Selection_Sort(ElementType A[], int N) 2 { 3 for(int i=0; i<N; i++) 4 { 5 int MinPosition = i; 6 int minNum = A[i]; 7 for(int j=i; j<N; j++) 8 { 9 if(A[j] < minNum)10 {11 minNum = A[j];12 MinPosition = j;13 }14 }15 ElementType tmp = A[i];16 A[i] = A[MinPosition];17 A[MinPosition] = tmp;18 }19 }
5. 头文件声明及main函数
1 #include <iostream> 2 #include <algorithm> 3 4 #define ElementType int 5 #define MAXNUM 100000000 6 7 using namespace std; 8 9 int cmp(const void *a, const void *b)10 {11 return *(int *)a - *(int *)b;12 }13 // 在这里插入上述几个函数14 int main()15 {16 ElementType n;17 cin >> n;18 ElementType *a = new ElementType[n];19 for(int i=0; i<n; i++)20 cin >> a[i];21 // Bubble_Sort(a, n);22 // Insertion_Sort(a, n);23 // Shell_Sort(a, n);24 // Selection_Sort(a, n);25 // sort(a, a+n);26 // stable_sort(a, a+n);27 qsort(a, n, sizeof(int),cmp);28 for(int i=0; i<n; i++)29 {30 if(i != n-1)31 cout << a[i] << " ";32 else33 cout << a[i];34 }35 return 0;36 }
各种排序算法的总结:
时间复杂度是的单位是ms,空间复杂度的单位是Kb,如果表格内有错误的话,请留言指正!
当然以下的排序函数只是一少部分,堆排序和归并排序代码量比较大,博主有空的时候再更新。通过表格可以看出,O(NlogN)真的快了不少!
排序算法 | 时间复杂度 | 稳定性 | case0:只有1个 | case1:11 | case2:10^3 | case3:10^4 | case4:10^5 | case5:10^5顺序 | case6:10^5逆序 | case7:10^5基本有序 | case8:10^5随机正整数 |
冒泡排序 | O(N^2) | 稳定 | 1 | 1 | 3 | 155 | 超时 | 39 | 超时 | 278 | 超时 |
插入排序 | O(N^2) | 稳定 | 1 | 1 | 2 | 21 | 1655 | 39 | 3266 | 53 | 1652 |
希尔排序 | O(NlgN) | 不稳定 | 1 | 1 | 1 | 6 | 50 | 41 | 42 | 41 | 42 |
选择排序 | O(N^2) | 稳定 | 1 | 1 | 2 | 38 | 3279 | 3265 | 3266 | 3267 | 3267 |
sort函数 | O(NlgN) | 不稳定 | 1 | 1 | 2 | 5 | 44 | 40 | 47 | 44 | 36 |
stable_sort函数 | O(NlgN) | 稳定 | 1 | 1 | 1 | 5 | 45 | 41 | 41 | 40 | 38 |
qsort函数 | O(NlgN) | 不稳定 | 1 | 1 | 2 | 6 | 49 | 42 | 43 | 43 | 41 |
排序算法 | 空间复杂度 | 稳定性 | case0:只有1个 | case1:11 | case2:10^3 | case3:10^4 | case4:10^5 | case5:10^5顺序 | case6:10^5逆序 | case7:10^5基本有序 | case8:10^5随机正整数 |
冒泡排序 | O() | 稳定 | 360 | 256 | 360 | 456 | 超时 | 1156 | 超时 | 1140 | 超时 |
插入排序 | O() | 稳定 | 236 | 284 | 232 | 260 | 1152 | 1260 | 1140 | 1184 | 1024 |
希尔排序 | O() | 不稳定 | 232 | 232 | 232 | 360 | 1128 | 1256 | 1128 | 1128 | 1000 |
选择排序 | O() | 稳定 | 284 | 232 | 232 | 376 | 1128 | 1144 | 1150 | 1180 | 1004 |
sort函数 | O() | 不稳定 | 232 | 236 | 364 | 376 | 1156 | 1152 | 1140 | 1180 | 1004 |
stable_sort函数 | O() | 稳定 | 232 | 232 | 232 | 360 | 1188 | 1188 | 1188 | 1188 | 1060 |
qsort函数 | O() | 不稳定 | 364 | 236 | 364 | 284 | 1144 | 1232 | 1144 | 1156 | 1136 |
中国大学MOOC-数据结构基础习题集、07-1、排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。