线性插入排序

线性插入排序 第九章 排序 P175 线性插入排序 void insertsort(struct node r[ n+1],int n) /* r[n+1]为一维数组，其中r[0]为监视哨，r[1]到r[n]为待排序的n个，排序好的记录仍放在r中*/ { for(i=2;i<=n;i++) /*共进行n-1趟*/ { r[0]=r[i]; /*r[0]为监视哨，也可做下边循环结束标志*/ j=i-1; while(r[j].key>r[0].key) { r[j+1]=r[j]; j--; } r[j+1]=r[0]; } } P176 折半插入排序 void binarysort(struct node r[ n+1],int n) /*按关键字递增的次序对记录r[1],r[2],......,r[n]进行折半插入排序 */ { for(i=2;i<=n;i++) { r[0]=r[i]; l=1; h=i-1; while(l<=h) { mid=(l+h)/2; if(r[0].key=l;j--) r[j+1]=r[j]; r[l]=r[0]; } } P178 希尔排序 rectype R[n+d1]; /* R[d1-1]为d1个监视哨*/ int d[t]; /* d[0]到d[t-1]为增量序列*/ SHELLSORT(R,d) Rectype R[ ]; int d[ ]; {int i，j，k，h; rectype temp; int maxint=32767; /*机器中最大整数*/ for (i=0;i=1;i--) adjust(r,i,n); /*建立初始堆*/ for(j=n;j>=2;j--) { x=r[1]; r[1]=r[j]; /*交换根结点和堆的最后一个结点*/ r[j]=x; Adjust (r,1,j-1) /*将r [1]至r[j-1]调整为堆*/ } } P185 一次划分及其排序的算法。 int partition(r,1,h) /*返回划分后被定的基准记录的位置*/ rectype R[ ]; /*对无序区R[1]到R[h]做划分*/ int 1,h; {int i,j; rectype temp; i=1;j=h temp=R[i]; /*初始化，temp为基准*/ Do{ While((R[j].key>=temp.key) && (i