quicksort.h

来自「各种算法的c语言程序」· C头文件 代码 · 共 82 行

#include<stdio.h>
#include<iostream.h>

#define Max  11  

typedef int KeyType;
typedef int ElemType;

int comp;

struct cell{
	KeyType  key;   //关键字域
	ElemType data;  //其它数据域
}; 
struct cell r[Max]; //定义数组


void  Create(){
	//构造一个含十个结点的序列
	int i=1;
	KeyType c;
    printf("请任意选10个小于和等于1000的整数:\n");
    while(i<Max){  //输入要排序的数组
		printf("r[%d].key=",i);
		fflush(stdin);
		scanf("%d",&c);
		fflush(stdin);
		if(c<=1000){  
			r[i].key=c;
            r[i].data=0;
			i++;}
		else printf("此数据无效，继续输入!\n");
	}
	printf("输入完毕!\n");
	printf("原始序列为:\n");
	for(i=0;i<10;i++) printf("%d ",r[i+1]);
}//Create

void Overturn(){
	//将顺序序列转换成逆序
	int i;
	KeyType   tempkey;
	ElemType  tempdata;
 	for(i=1;i<=(Max/2);i++){
		//交换key
		tempkey=r[i].key;
		r[i].key=r[Max-i].key;
		r[Max-i].key=tempkey;
	    //将data进行交换
		tempdata=r[i].data;
		r[i].data=r[Max-i].data;
		r[Max-i].data=tempdata;
	}
}

void quicksort(int s,int t)//快速排序程序
{ //把r[s]到r[t]的元素进行排序
	int i,j;
	i=s;j=t;
	if(s<t)
	{  
		r[0]=r[s];
		do{
			while(comp++,j>i&&r[j].key>=r[0].key) j--;
			if(comp++,i<j){//将r[j]移到r[i]的位置上
				r[i]=r[j];
				i++;}

            while(comp++,j>i&&r[0].key>=r[i].key) i++;
			if(i<j){//将r[i]移到r[j]的位置上
				r[j]=r[i];
				j--;}
		}while(comp++,i<j);
		r[i]=r[0];//将r[0]移到r[i]的位置上

		quicksort(s,j-1);//将无序记录分为两部分，然后
		                //递归调用快速排序
		quicksort(j+1,t);
	}
	
	
}