习题4-快速排序.c

数据结构各章实验源代码； 数据结构实验源代码

#include  "datastru.h"
#include  <stdio.h>

int partition(RECNODE *r, int *low, int *high)
{/*一趟快速排序,返回i,产生了两个独立的待排子序列*/
	int i, j;
	RECNODE	 temp;

	i = *low;  j = *high;
	temp = r[i];                                         /*枢轴记录保存在temp变量中*/
	do{ while((r[j].key >= temp.key) && (i < j))  j--;   /*j指针记录和枢轴记录比较*/
	    if(i < j)    { r[i] = r[j];   i++;}
	   while((r[i].key <= temp.key) && (i < j))   i++;   /*i指针记录和枢轴记录比较*/
	   if(i < j)     { r[j] = r[i];   j--;}
          }while(i != j);
	r[i] = temp;                                         /*枢轴记录的排序位置确定在i*/
	return i;
}

void quicksort(RECNODE *r, int start, int end)
{/*快速排序*/
	int i;
	if(start < end)
	   { i = partition(r, &start, &end);  /*一趟快速排序,返回i,产生了两个独立的待排子序列*/
	     quicksort(r, start, i - 1);      /*对两个独立的待排子序列分别递归调用快速排序算法*/
	     quicksort(r, i + 1,end);}
}

main( )
{ RECNODE  a[MAXSIZE];
  int  i, j, k, len, start;

 printf("\n\n输入待排序数据(整数，以空格隔开，0 结束) : "); k = 0; scanf("%d",&j);
 while(j != 0) { k++; a[k].key = j; scanf("%d",&j); }
 len = k;  start = 1;
 printf("\n排序前 : ");
 for (i = 0; i < len; i++)   printf("  %d",a[i+1].key);
 printf("\n");
 quicksort (a,start,len);
 printf("\n\n排序后 : ");
 for (i = 0; i < len; i++)   printf("  %d",a[i+1].key);
 printf("\n\n");
}