qs.c

实训报告编码译码

/*              快速排序算法					*/
/*		作者：	毛剑辉		学号：200428014825038	*/
/*		日期：2004年10月3日				*/

int quicksort(int p[],int n);
extern int insertsort(int p[], int n);
static int partition(int p[],int n,int *m);
int quickSort(int p[],int n);
static int quick_sort(int p[],int n);




static struct stackframe 
{ 
	int * list;
	int length; 
};
static struct stackframe sp[64]; 	/* 栈指针 */
static unsigned int	randx; 		/* 伪随机数 */
#define M 16

int quicksort(int p[],int n)
{
	int op=0;
	int i,k;
	int *h,l;
	int m; 				/* 基准值的位置 */
	struct stackframe *fp; 		/* 帧指针*/
	struct stackframe *stp; 	/* 栈顶指针 */ 

	if (n<=16)
		return insertsort(p,n);
	randx=p[0]%7875;

	for (i=0,k=n; k>0; k>>=1,i++); /* i=[lg(n)] */
	stp=sp+i;
	fp=sp;
	fp->list=p;
	fp->length=n;
	while (fp>=sp) 
	{

		h=fp->list;
		l=fp->length;
		while (l>M && fp<=stp) 
		{
			op+=partition(h,l,&m);
			fp->list=h+m+1;
			fp->length=l-m-1;
			fp++;
			l=m; 
		}
		fp--;
	}
	op+=insertsort(p,n);
	return op;
}

/*
 * 基准值
 */
static int partition(int p[],int n,int *m )	/* 返回的基准值的位置 */
{
	int i=0; 				/* 头指针 */
	int j=n-1; 				/* 尾指针 */
	int pivot; 				/* 基准值 */
	int k; 
	if (n<=1)
		return 0; 
	//randx=(randx*421+1663)%7875; 		/* 线性同余伪随机数 */
	//k=randx%n;
	/* 随机选择某个位置的元素作为基准值并保存它,接着把头指针指向的元素复制到这个位置上 */
	k = n / 2;
	pivot=p[k];
	p[k]=p[i];
						/* p[i] 已被交换到 p[k]，可以覆盖 */
	while (i<j) 
	{ 					/* 头指针先于尾指针 */
		while (i<j && p[j]>=pivot) 	/* 尾指针指向的元素大于基准值 */
		{
			j--;			/* 前移尾指针 */

		}
		if (i<j)  
			p[i++]=p[j]; 		/* 替换当前p[i]内容为p[j]的内容, 后移头指针 */
						/* p[j] 已被交换可以覆盖 */
		
		while (i<j && p[i]<=pivot) 	/* 头指针指向的元素小于基准值 */
		{
			i++; 			/* 后移头指针 */

		}
		if (i<j)
			p[j--]=p[i]; 		/* 替换当前p[j]内容为p[i]的内容, 前移尾指针 */

						/* p[i] 已被交换可以覆盖 */
	}
	/* 如果最后一次交换的是 p[j]，则 i 指针会移动成 i=j */
	p[i]=pivot; 				/* 把保存的基准值保存到当前位置上 */
	*m=i; 					/* 返回基准值当前的位置 */
	return n;
}

/**************************************/
/*   下面是递归原型实现		     */ 
/**************************************/
int quickSort(int p[],int n)
{
	if (n<=16)
		return insertsort(p,n);
	//randx=p[0]%7875;
	return quick_sort(p,n);
}

static int quick_sort(int p[],int n)
{
	int op=0; 

	int m; 
    
	if (n>16) { 
		op+=partition(p,n,&m);
		op+=quick_sort(p,m);
		op+=quick_sort(p+m+1,n-m-1);
	}
	else 
		insertsort(p,n);
	
	return op; 
}