复制
收藏
提问
简洁
#include <stdio.h> #include <stdlib.h> #define MAXSIZE 20 typedef struct { int key; char *otherinfo; }ElemType; typedef struct { ElemType *r; int length; }SqList; void InsertSort(SqList &L) { int i,j; for(i=2;i<=L.length;++i) if(L.r[i].key<L.r[i-1].key) { L.r[0]=L.r[i]; L.r[i]=L.r[i-1]; for(j=i-2; L.r[0].key<L.r[j].key;--j) L.r[j+1]=L.r[j]; L.r[j+1]=L.r[0]; } } void BInsertSort(SqList &L){ int i,j,low,high,m; for(i=2;i<=L.length;++i) { L.r[0]=L.r[i]; low=1; high=i-1; while(low<=high) { m=(low+high)/2; if(L.r[0].key<L.r[m].key) high=m-1; else low=m+1; } for(j=i-1;j>=high+1;--j) L.r[j+1]=L.r[j]; L.r[high+1]=L.r[0]; } } void ShellInsert(SqList &L,int dk) { int i,j; for(i=dk+1;i<=L.length;++i) if(L.r[i].key<L.r[i-dk].key) { L.r[0]=L.r[i]; for(j=i-dk;j>0&& L.r[0].key<L.r[j].key;j-=dk) L.r[j+dk]=L.r[j]; L.r[j+dk]=L.r[0]; } } void ShellSort(SqList &L,int dt[ ],int t){ int k; for(k=0;k<t;++k) ShellInsert(L,dt[k]); } void BubbleSort(SqList &L) { int m,j,flag; ElemType t; m=L.length-1; flag=1; while((m>0)&&(flag==1)) { flag=0; for(j=1;j<=m;j++) if(L.r[j].key>L.r[j+1].key) { flag=1; t=L.r[j];L.r[j]=L.r[j+1];L.r[j+1]=t; } --m; } } int Partition(SqList &L,int low,int high) { int pivotkey; L.r[0]=L.r[low]; pivotkey=L.r[low].key; while(low<high) { while(low<high&&L.r[high].key>=pivotkey) --high; L.r[low]=L.r[high]; while(low<high&&L.r[low].key<=pivotkey) ++low; L.r[high]=L.r[low]; } L.r[low]=L.r[0]; return low; } void QSort(SqList &L,int low,int high) { int pivotloc; if(low<high) { pivotloc=Partition(L,low,high); QSort(L,low,pivotloc-1); QSort(L,pivotloc+1,high); } } void QuickSort(SqList &L) { QSort(L,1,L.length); } void Create_Sq(SqList &L) { int i,n; printf("请输入数据个数，不超过%d个\n",MAXSIZE); scanf("%d",&n); printf("请输入待排序的数据:\n"); while(n>MAXSIZE) { printf("个数超过上限，不能超过%d，请重新输入\n",MAXSIZE); scanf("%d",&n); } for(i=1;i<=n;i++) { scanf("%d",&L.r[i].key); L.length++; } } void show(SqList L) { int i; for(i=1;i<=L.length;i++) printf("%d ",L.r[i].key); printf("\n"); } int main() { SqList L; L.r=(ElemType*) malloc(sizeof(ElemType)*(MAXSIZE+1)); L.length=0; Create_Sq(L); InsertSort(L); printf("直接插入排序后的结果为：\n"); show(L); L.length=0; Create_Sq(L); BInsertSort(L); printf("折半插入排序后的结果为：\n"); show(L); printf("希尔排序：\n"); L.length=0; Create_Sq(L); int i,t; int *dt=(int*) malloc(sizeof(int)*MAXSIZE); printf("请输入增量个数：\n"); scanf("%d",&t); for(i=0;i<t;i++) { printf("第%d个增量:\n",i+1); scanf("%d",&dt[i]); } ShellSort(L,dt,t); printf("希尔排序后的结果为：\n"); show(L); L.length=0; Create_Sq(L); BubbleSort(L); printf("冒泡排序后的结果为：\n"); show(L); L.length=0; Create_Sq(L); QuickSort(L); printf("快速排序后的结果为：\n"); show(L); }时间复杂度，空间复杂度
4月前
全网
文档
学术
百科
知识库
回答简洁模式
深入研究一些
在C语言中实现不同排序算法时，分析其时间复杂度和空间复杂度对于理解算法性能至关重要。以下是几种常见排序算法的时间复杂度和空间复杂度的分析：
1. 直接插入排序
- 时间复杂度：平均和最坏情况下都是 O(n^2)，最好情况下是 O(n)。
- 空间复杂度：O(1)，因为它是就地排序算法。
- 稳定性：稳定
- 复杂性：简单
2. 二分插入排序
- 时间复杂度：最坏情况下是 O(n^2)，最好情况下是 O(log n)。
- 空间复杂度：O(1)，同样是就地排序算法。
- 稳定性：不稳定
3. 希尔排序
- 时间复杂度：平均情况下是 O(n log n)，但最坏情况下是 O(n^2)。实验表明，当 n 较大时，希尔排序的性能接近 O(n^1.3)。
- 空间复杂度：O(1)，就地排序。
- 稳定性：不稳定
- 复杂性：较复杂，因为需要选择合适的增量序列。
4. 直接选择排序
- 时间复杂度：在所有情况下都是 O(n^2)。
- 空间复杂度：O(1)，就地排序。
- 稳定性：不稳定
5. 堆排序
- 时间复杂度：平均和最坏情况下都是 O(n log n)。
- 空间复杂度：O(1)，就地排序。
- 稳定性：不稳定
6. 冒泡排序
- 时间复杂度：平均和最坏情况下都是 O(n^2)，最好情况下是 O(n)。
- 空间复杂度：O(1)，就地排序。
- 稳定性：稳定
7. 快速排序
- 时间复杂度：平均情况下是 O(n log n)，但最坏情况下是 O(n^2)。
- 空间复杂度：O(n log n)，因为需要递归调用。
- 稳定性：不稳定
8. 归并排序
- 时间复杂度：在所有情况下都是 O(n log n)。
- 空间复杂度：O(n)，需要额外的存储空间来执行合并操作。
- 稳定性：稳定
9. 基数排序
- 时间复杂度：O(d(n+r))，其中 d 是位数，r 是基数。
- 空间复杂度：O(n+r)，需要额外的存储空间来存放中间结果。
- 稳定性：稳定
在实际应用中，选择哪种排序算法取决于具体问题的需求，包括数据规模、内存限制、是否需要稳定性等因素。时间复杂度和空间复杂度的分析帮助我们预估算法的执行时间和内存占用，从而选择最合适的算法。
你觉得结果怎么样？