quick.h

来自「各种排序方法源码」· C头文件 代码 · 共 41 行

#include<string.h>
//------------------------------交换枢轴两边数据函数--------------------------------//
int partition(node *d,int low,int high,int &jc,int &bc)
{//交换顺序表d中的从low到high的子表记录，使枢轴记录到位，并返回其所在位置，
//此时在它之前（后）的记录均不大（小）于它
	int pi;
	d[0].data=d[low].data;   //用子表的第一个记录作枢轴记录
	strcpy(d[0].c,d[low].c);
	jc++;
    pi=d[low].data;   //枢轴记录关键字
	while(low<high)       //从表的两端交替地向中间扫描
	{
		bc++;
		while(low<high&&d[high].data>=pi)
		{--high;bc++;}
			d[low].data=d[high].data;	 //将比枢轴记录小的记录移到低端
	      strcpy(d[low].c,d[high].c);
		  jc++;
		while(low<high&&d[low].data<=pi)
		{++low;bc++;}
         	d[high].data=d[low].data;	 //将比枢轴记录大的记录移到高端
	      strcpy(d[high].c,d[low].c);
		  jc++;
	}
	d[low].data=d[0].data;	    //枢轴记录到位
	strcpy(d[low].c,d[0].c);
	jc++;
		  return low;    //返回枢轴位置
} 
//-------------------------------快速排序函数----------------------------------------//
void quicksort(node *d,int low,int high,int &jc,int &bc)
{//对顺序表d中的从low到high的子列作快速排序
	int piv;
	if(low<high)       //长度大于1
	{
		bc++;
		piv=partition(d,low,high,jc,bc);  //将子列一分为二
		quicksort(d,low,piv-1,jc,bc);    //对低子表递归排序，piv是枢轴位置
		quicksort(d,piv+1,high,jc,bc);   //对高子表递归排序
	}
}