#include <stdio.h>
# include "time.h"# include "stdlib.h" #define LEN 8typedef struct { int key[11]; int length;}L;void printSort(L l){ for(int i=1;i<=10;i++) { printf("%d\t",l.key[i]); } }L createRand(){ L l; l.length=0; for(int i=1;i<11;i++) { l.key[i]=rand()%100; l.length=l.length+1; } return l;}void InsertSort(L l){ printf("\t|-------------------|\n"); printf("\t| 直接插入排序 |\n"); printf("\t|-------------------|\n随机数:\n"); printSort(l);printf("\n"); for(int i=2;i<=l.length;i++) { if(l.key[i]<=l.key[i-1]) { l.key[0]=l.key[i]; for(int j=i-1;l.key[0]<l.key[j];j--) l.key[j+1]=l.key[j]; l.key[j+1]=l.key[0]; } printf("i=%d ",i); printSort(l); }}///void ShellLinesert(L &l,int dk) //希尔排序{ for(int i=dk+1;i<=l.length;i++) { if(l.key[i]<l.key[i-dk]) { l.key[0]=l.key[i]; for(int j=i-dk;j>0&&(l.key[0]<l.key[j]);j-=dk) l.key[j+dk]=l.key[j]; l.key[j+dk]=l.key[0]; } }} void ShellSort(L l,int dk[],int t){ printf("\t|-------------------|\n"); printf("\t| 希尔排序 |\n"); printf("\t|-------------------|\n随机数:\n"); printSort(l);printf("\n"); for(int k=0;k<t;k++) { ShellLinesert(l, dk[k]) ; printf("i=%d ",k); printSort(l); }}//void BubbleSort(L l){ printf("\t|-------------------|\n"); printf("\t| 冒泡排序 |\n"); printf("\t|-------------------|\n随机数:\n"); printSort(l);printf("\n"); bool flag=true; int temp; for(int i=1;i<=l.length-1&&flag;i++) { flag=false; for(int j=1;j<=l.length-i;j++) { if(l.key[j]>l.key[j+1]) { temp=l.key[j]; l.key[j]=l.key[j+1]; l.key[j+1]=temp; flag=true; } } printf("i=%d ",i); printSort(l); }}// int Position(L &l,int i,int j){ while(i<j) { while(i<j && l.key[j]>=l.key[0]) j--; l.key[i]=l.key[j]; while(i<j && l.key[i]<=l.key[0]) i++; l.key[j]=l.key[i]; } return i;}void QuictSort(L &l,int i,int j) //快速排序{ int p; if(i<j) { l.key[0]=l.key[i]; p=Position( l,i,j); l.key[p]=l.key[0]; QuictSort( l, i,p-1); QuictSort( l, p+1,j); } printSort(l); }void SelectSort(L l)//简单选择排序{ printf("\t|-------------------|\n"); printf("\t| 简单选择排序 |\n"); printf("\t|-------------------|\n随机数:\n"); printSort(l);printf("\n"); int k,temp,j,i; for( i=1;i<l.length;i++) { k=i; for( j=i+1;j<=l.length;j++) { if(l.key[k]>l.key[j]) k=j; } if(k!=i) { temp=l.key[k]; l.key[k]=l.key[i]; l.key[i]=temp; } printf("i=%d ",i); printSort(l); } } /// void Merge (L l1,L &l2,int low,int mid,int hight){ int i=low; int j=mid+1; int k=low; while(i<mid&&j<hight) { if(l1.key[i]<=l1.key[j]) { l2.key[k]=l1.key[i]; i++; } else { l2.key[k]=l1.key[j]; j++; } k++; } while(i<=mid) { l2.key[k]=l1.key[i]; k++; i++; } while(j<=hight) { l2.key[k]=l1.key[j]; k++; j++; } l2.length=k;}void msort(L l1,L &l2,int low,int hight){ int mid; if(low==hight) { l2.key[low]=l1.key[low]; } else { mid=(low+hight)/2; msort(l1,l2,low,mid); msort(l1,l2,mid+1,hight); Merge(l1,l2,low,mid,hight); }}void MergerSort(L &l){ msort(l,l,1,l.length); } void SortCompare() //时间性能比较{ printf("\t|--------------------------|\n"); printf("\t| 时间复杂度的比较 |\n"); printf("\t|--------------------------|\n"); printf("直接插入排序\tO(n^2)\n"); printf("希尔排序\tO(n^2)\n"); printf("冒泡排序\tO(n^2)\n"); printf("简单选择排序\tO(n^2)\n"); printf("快速排序\tO(n^2)\n"); printf("归并排序\tO(n)\n");} void menu_select() //系统主界面{ printf(" 欢迎使用排序综合系统\n"); printf("============================================================\n"); printf(" *1.直接插入排序 *2.希尔排序\n"); printf(" *3.冒泡排序 *4.快速排序\n"); printf(" *5.简单选择排序 *6.归并排序\n"); printf(" *7.时间性能比较 *0.退出排序系统\n"); printf("============================================================\n"); printf("请选择0-7：");}void main(){ L l=createRand(); int item; while(item!=0) { menu_select() ; scanf("%d",&item); switch(item) { case 1:InsertSort( l);break; case 2: int a[2]; a[0]=5,a[1]=3;a[2]=1;ShellSort(l,a, 3);break; case 3:BubbleSort(l);break; case 4: printf("\t|-------------------|\n"); printf("\t| 冒泡排序 |\n"); printf("\t|-------------------|\n随机数\n"); printSort(l);printf("\n"); QuictSort( l,0,10);break; case 5:SelectSort(l);break; case 6: ;break; case 7:SortCompare();break; } }}