快速排序.cpp

数据结构学习中常用的程序．用c语言编写．vc＋＋６．０运行通过

#include <stdio.h>
typedef int InfoType;

#define n 10					//假设的文件长度，即待排序的记录数目
typedef int KeyType;			//假设的关键字类型
typedef struct {				//记录类型
	KeyType key;				//关键字项
	InfoType otherinfo;			//其它数据项，类型InfoType依赖于具体应用而定义
} RecType;
typedef RecType SeqList[n+1];	//SeqList为顺序表类型，表中第0个单元一般用作哨兵
int Partition(SeqList R,int i,int j);

void main()
{
	void QuickSort(SeqList R,int low,int high);
	int i;
	SeqList R;
	printf("请输入欲排序的数：");
	for (i=1;i<=n;i++)
		scanf("%d",&R[i].key);
	printf("排序前：");
	for (i=1;i<=n;i++)
		printf("%d ",R[i].key);
	printf("\n");
	QuickSort(R,1,n);
	printf("排序后：");
	for (i=1;i<=n;i++)
		printf("%d ",R[i].key);
	printf("\n");
}

void QuickSort(SeqList R,int low,int high)
{	//对R[low..high]快速排序
	int pivotpos;						//划分后的基准记录的位置
	if(low<high){						//仅当区间长度大于1时才须排序
		pivotpos=Partition(R,low,high);	//对R[low..high]做划分
		QuickSort(R,low,pivotpos-1);	//对左区间递归排序
		QuickSort(R,pivotpos+1,high);	//对右区间递归排序
	}
}

int Partition(SeqList R,int i,int j)
{//调用Partition(R,low,high)时，对R[low..high]做划分，并返回基准记录的位置
	RecType pivot=R[i];		//用区间的第1个记录作为基准
	while(i<j){				//用区间两端交替向中间扫描，直至i=j为止
		while(i<j && R[j].key>=pivot.key)		//pivot相当于在位置i上
			j--;			//从右向左扫描，查找第1个关键字小于pivot.key的记录R[j]
		if(i<j)				//表示找到的R[j]的关键字<pivot.key
			R[i++]=R[j];	//相当于交换R[i]和R[j]，交换后i指针加1
		while(i<j && R[i].key<=pivot.key)	//pivot相当于在位置j上
			i++;			//从左向右扫描，查找第1个关键字大于pivot.key的记录R[i]
		if(i<j)				//表示找到了R[i]，使R[i].key>pivot.key
			R[j--]=R[i];	//相当于交换R[i]和R[j]，交换后j指针减1
	}
	R[i]=pivot;				//基准记录已被最后定位
	return i;
}