quicksort.cpp

随机生成500个数字并进行快速排序

//#include "conio.h"
#include "stdio.h"
#include "stdlib.h"
#include "time.h"
#include "sys/timeb.h"

typedef int KeyType;		// 定义关键字类型为整数类型

#define MAXSIZE   500		// 数组的最大容量
#define OUTFORMAT "%10d"	// 输出格式控制符

typedef struct
{
	KeyType key;			// 关键字项,若有其它数据项可以这里添加
}RedType;

typedef struct
{
	RedType r[MAXSIZE+1];	// r[0]闲置
	int length;				// 顺序表的长度
}SqList;

void CreateSqList(SqList &L)	// 创建顺序表
{
	int i=1;
	srand((unsigned)time(NULL));// 初始化随机数产生器
    printf("    快速排序\n\n随机产生 %d 个数据:\n\n",MAXSIZE);
	while(i<=MAXSIZE)
	{
		L.r[i].key=rand();		// 获得随机数
		printf(OUTFORMAT,L.r[i].key);
		i++;
	}
	L.length=MAXSIZE;
}

int Partition(SqList &L,int low,int high)	// 快速排序程序的具体实现
{
    KeyType pivotkey;
    L.r[0]=L.r[low];		// 用子表的第一个记录作枢轴记录
    pivotkey=L.r[low].key;	// 枢轴记录关键字
    while(low<high)
    {
		while(low<high&&L.r[high].key>=pivotkey)  --high;	// 先从后往前扫描,找出小者
		L.r[low]=L.r[high];	// 将比枢轴记录小的记录移到低端
		while(low<high&&L.r[low].key<=pivotkey)  ++low;	// 再从前往后扫描,找出大者
		L.r[high]=L.r[low];	// 将比枢轴记录大的记录移到高端
    }
    L.r[low]=L.r[0];		// 枢轴记录到位
    return low;
}

void QSort(SqList &L,int low,int high)		// 对顺序表L中的子序列作快速排序
{
    int pivotloc;
    if(low<high)	// 长度大于1
    {
		pivotloc=Partition(L,low,high);	// 一分为二
		QSort(L,low,pivotloc-1);		// 对低端子表递归排序
		QSort(L,pivotloc+1,high);		// 对高端子表递归排序
    }
}

void main(void)
{
    struct _timeb timebuffer;
	time_t Start,End;					// 秒级
	unsigned short StartTime,EndTime;	// 毫秒级
	time(&Start);			// 获得当前时间(秒)
	_ftime(&timebuffer);	// 获得当前时间(毫秒)
	StartTime=timebuffer.millitm;
	int i;
    SqList L;
	system("cls");			// 清屏
    CreateSqList(L);		// 初始化顺序表
    QSort(L,1,L.length);	// 对顺序表L作快速排序
    printf("\n\n排序结果如下所示:\n\n");
    for(i=1;i<=L.length;i++)// 显示出最终结果
		printf(OUTFORMAT,L.r[i].key);
	time(&End);				// 再次获得当前时间(秒)
	_ftime(&timebuffer);	// 再次获得当前时间(毫秒)
	EndTime=timebuffer.millitm;
	if(EndTime>=StartTime)
		printf("\n\n\t\t\t    共耗时 %.0f 秒 %hu 毫秒 !\n",\
			difftime(End,Start),EndTime-StartTime);
	else
		printf("\n\n\t\t\t    共耗时 %.0f 秒 %hu 毫秒 !\n",\
			difftime(End,Start)-1,1000+EndTime-StartTime);
    system("pause");	// 暂停
}