4.快速排序
详细设计
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define Max_Size 5000
typedef int KeyType;
typedef int OtherType;
typedef struct
{
KeyType key;
OtherType other_data;
}RecordType;
int QKPass(RecordType r[],int low, int high )
//对记录数组r[low..high]用快速排序算法进行排序*/
{
r[0]=r[low]; //将枢轴记录移至数组的闲置分量
int pivotkey=r[low].key;//枢轴记录关键字
while(low<high)
{
while(low<high && r[high].key>=pivotkey)
--high; // high从右到左找小于x.key的记录if(low<high) //确保low始终小于high
r[low++]=r[high]; //将比枢轴记录小的记录移到低端
while(low<high && r[low].key<pivotkey)
++low; // low从左到右找小于x.key的记录if(low<high)
r[high--]=r[low]; //将比枢轴记录小的记录移到高端}
r[low]=r[0]; //枢轴记录移到正确位置
return low;
}
void QKSort(RecordType r[],int left,int right)
{
if(left<right)
{
int pivot;
pivot=QKPass(r,left,right);
QKSort(r,left,pivot-1);
QKSort(r,pivot+1,right);
}
} // QKPass
void main()
{
int i;
RecordType r[Max_Size];
int len;
printf("请输入待排序记录的长度:");
scanf("%d",&len);
for(i=1;i<=len;i++)
srand((unsigned)time(NULL));
for(i=1;i<=len;i++)
r[i].key =rand();
printf("\n待排序记录:\n");
for(i=1;i<=len;i++)
printf("%6d ",r[i].key);
printf("\n");
QKSort(r,1,len);
printf("\n排序后的记录:\n");
for(i=1;i<=len;i++)
printf("%6d ",r[i].key);
printf("\n\n");
}
测试结果。