首页 > 代码库 > 中国大学MOOC-数据结构基础习题集、07-1、排序

中国大学MOOC-数据结构基础习题集、07-1、排序

2024-11-03 05:23:39   208人阅读

题目链接：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:11case2:10^3case3:10^4case4:10^5case5:10^5顺序case6:10^5逆序case7:10^5基本有序case8:10^5随机正整数
冒泡排序O(N^2)稳定113155超时39超时278超时
插入排序O(N^2)稳定112211655393266531652
希尔排序
O(NlgN)
不稳定11165041424142
选择排序O(N^2)稳定1123832793265326632673267
sort函数O(NlgN)不稳定11254440474436
stable_sort函数O(NlgN)稳定11154541414038
qsort函数O(NlgN)不稳定11264942434341

　　

排序算法空间复杂度稳定性case0：只有1个case1:11case2:10^3case3:10^4case4:10^5case5:10^5顺序case6:10^5逆序case7:10^5基本有序case8:10^5随机正整数
冒泡排序O()稳定360256360456超时1156超时1140超时
插入排序O()稳定23628423226011521260114011841024
希尔排序O()不稳定23223223236011281256112811281000
选择排序O()稳定28423223237611281144115011801004
sort函数O()不稳定23223636437611561152114011801004
stable_sort函数O()稳定23223223236011881188118811881060
qsort函数O()不稳定36423636428411441232114411561136

中国大学MOOC-数据结构基础习题集、07-1、排序


联系
我们