插入排序

插入排序 #include"stdio.h" #include"stdlib.h" #define MaxSize 50 typedef int KeyType; typedef struct { KeyType key; }DataType; typedef struct { DataType data[MaxSize]; int length; }SqList; void InitSeqList(SqList *L,DataType a[],int n) { int i; for(i=1;i<=n;i++) { L->data[i]=a[i-1]; } L->length=n; } void InsertSort(SqList *L) { int i,j; DataType t; for(i=1;ilength;i++) t=L->data[i+1]; j=i; while(j>-1&&t.keydata[j].key) { L->data[j+1]=L->data[j]; j--; } L->data[j+1]=t; } void ShellInsert(SqList *L,int c) { int i,j; DataType t; for(i=c+1;i<=L->length;i++) if(L->data[i].keydata[i-c].key) { t=L->data[i]; for(j=i-c;j>0&&t.keydata[j].key;j=j-c) L->data[j+c]=L->data[j]; L->data[j+c]=t; } } void ShellInsertSort(SqList *L,int delta[],int m) { int i; for(i=0;ilength;i++) { t=L->data[i+1]; low=1,high=i; while(low<=high) { mid=(low+high)/2; if(L->data[mid].key>t.key) high=mid-1; else low=mid+1; } for(j=i;j>=low;j--) L->data[j+1]=L->data[j]; L->data[low]=t; } } void DispList(SqList L,int n) { int i; for(i=1;i<=n;i++) printf("%4d",L.data[i].key); printf("\n"); } void main() { DataType a[]={56,22,67,32,59,12,89,26,48,37}; int delta[]={5,3,1}; int n=10,m=3; SqList L; InitSeqList(&L,a,n); printf("排序前: "); DispList(L,n); InsertSort(&L); printf("直接插入排序结果: "); DispList(L,n); InitSeqList(&L,a,n); printf("排序前: "); DispList(L,n); BinInsertSort(&L); printf("折半插入排序结果: "); DispList(L,n); InitSeqList(&L,a,n); printf("排序前: "); DispList(L,n); ShellInsertSort(&L,delta,m); printf("希尔排序结果:"); DispList(L,n); }