直接插入排序_折半插入_2路插入_希尔排序.doc

#include stdio.h #include stdlib.h #include iostream.h void isort(int a[],int len) { int i,j,insert; int index; for(i=1;ilen;i++) { index=i-1; insert=a[i]; while(index=0inserta[index]) { a[index+1]=a[index]; index--; } a[index+1]=insert; } } void halfinsert(int a[],int len) { int i,j; int low=0,high=0,mid; int insert; for(i=1;ilen;i++) { low=0;high=i-1; int insert; insert=a[i]; while(low=high) { mid=(low+high)/2; if(insert=a[mid]) low=mid+1; else high=mid-1; } for(j=i-1;j=high+1;j--) { a[j+1]=a[j]; } a[high+1]=insert; } } void twoinsert(int a[],int b[],int len) { int i; int j; int first,final; first=final=0;//first、final分别指示d中排好序的记录的第1个和最后1个记录的位置。 b[first]=a[0]; for(i=1;ilen;i++) { if(a[i]b[first])//待插入记录小于d中最小值，插入到d[first]之前（不需移动d数组的元素 { first=(first-1+len)%len; b[first]=a[i]; } else if(a[i]=b[final])//待插入记录大于d中最小值，插入到d[final]之后（不需移动d数组的元素）。 { final=final+1; b[final]=a[i]; } else //待插入记录大于d中最小值，小于d中最大值，插入到d的中间（需要移动d数组的元素 { j=final; final++; while(a[i]b[j]) { b[(j+1+len)%len]=b[j]; j=(j-1+len)%len; } b[j+1]=a[i]; } } for ( i = 0; i len; ++i ) { a[i]=b[(i+first)%len]; } } void shellsort(int a[],int n) { int d; int i,j,temp; d=n/2; int len; len=n; while(d=1) { for(i=d;ilen;i++) { temp=a[i]; j=i-d; while(j=0a[j]temp) { a[j+d]=a[j]; j=j-d; } a[j+d]=temp; } d=d/2; } } void display(int a[],int len) { int i; for(i=0;ilen;i++) couta[i] ; coutendl; } int main() { int i; int choice; int a[8]={3,2,5,4,1,7,9,6}; int len=sizeof(a)/sizeof(int); int b[10]; printf(please input the choice(0,1,2,3):\n); scanf(%d,choice); switch(choice) { case 0: printf(插入排序:\n); isort(a,len); display(a,len); break; case 1: printf(折半插入:\n); halfinsert(a,len); display(a,len); break; case 2: printf(2_路插入:\n); twoinsert(a,b,len); display(a,len); break; case