quicksort.cpp

这个是编译原理课程的词法分析器

// 
// 快速排序。
//

#include "stdlib.h"
#include "stdio.h"


/*
 * 顺序表的定义
 */ 
#define MAX 100	// MAX代表顺序表的最大长度,即排序数据个数的最大值

typedef struct Seqlist{
	int r[MAX+1]; //r[0]闲置或用作哨兵
	int length;   //顺序表的长度
} SeqList;    	//程序中用SeqList定义顺序表变量


/* 
 * 输出对子表L.r[low..high]的一次划分,
 * 格式为:{低子表}枢轴{高子表};
 * 如果pivotloc为-1,则是输出排序前表的所有内容;
 * 如果pivotloc为-2,则输出排序结果.
 */
void output(SeqList *L,int low,int high,int pivotloc){
	int i;
	if(pivotloc==-1||pivotloc==-2){	 
		if(pivotloc==-1)
			printf("初始状态: {");
		else
			printf("排序结果: {");
		for(i=low;i<=high;i++)
			printf("%d ",L->r[i]);
		printf("}");
	}else{	 	 
		printf("划分结果：{");
		for(i=low;i<pivotloc;i++)
			printf("%d ",L->r[i]);	 
		printf("}%d",L->r[pivotloc]);
		printf("{");
		for(i=pivotloc+1;i<=high;i++) 
			printf("%d ",L->r[i]);
		printf("}");
	}
	printf("\n");		
}

/*
 * 划分顺序表L中子表r[low..high],此时在它之前(后)的记录均不大(小)于它.
 */
int partition(SeqList *L,int low,int high){
	int pivotkey;
	int temp1=low,temp2=high;
	L->r[0]=L->r[low];						// 用子表的第一个记录作为枢轴记录
	pivotkey=L->r[low];
	while(low<high){							// 从表的两端交替向中间扫描     		
		while(low<high&&L->r[high]>=pivotkey)
			--high;
		L->r[low]=L->r[high];				// 将比枢轴小的记录移到低端
		while(low<high&&L->r[low]<=pivotkey)
			++low;
		L->r[high]=L->r[low];				// 将比枢轴大的记录移到高端
	}
	L->r[low]=L->r[0];						// 枢轴记录到位     
	output(L,temp1,temp2,low);		// 输出该次划分的结果
	return low;										// 返回枢轴位置
}


/*
 * 对顺序表L中的子序列L.r[low..high]作快速排序.
 */
void quicksort(SeqList* L,int low,int high){
	int pivotloc;
	if(low<high)
		pivotloc=partition(L,low,high);
	if (low<pivotloc-1) 
		// 对低子表递归排序,pivotloc是枢轴位置
		quicksort(L,low,pivotloc-1);                   
	if(high>pivotloc+1) 
		// 对高子表递归排序
		quicksort(L,pivotloc+1,high);                  
}

/*
 * 主函数.
 */
void main(){
	SeqList L;
	int i,num;
	printf("请输入要排序的元素个数:");
	scanf("%d",&num);
	printf("请输入要排序的元素(数据元素之间用空格分隔):");
	for(i=1;i<=num;i++)
	scanf("%d",&L.r[i]);	  	
	L.length=num;
  // 输出排序前的顺序表	
	output(&L,1,L.length,-1); 
	// 快速排序         	
	quicksort(&L,1,L.length); 
	// 输出排序后的结果             
	output(&L,1,L.length,-2);          
}