快速排序算法

 /*
 快速排序算法之所以得到广泛的应用是因为它在很多情况下都能运行的很好,其他方法可能更合适解决某些特定的情况,而快速排序算法可以比其他方法处理更多的排序问题,而且它通常会比其他可选择的方案更快.
 */


/*
基本快速排序算法
*/
 int partition(Item a[], int l, int r);
 void quicksort(Item a[], int l, int r)
 { 
 	int i;
 	if (r <= l) return;
 	i = partition(a, l, r);
 	quicksort(a, l, i-1);
 	quicksort(a, i+1, r);
 }
 int partition(Item a[], int l, int r)
 { 
 	int i = l-1, j = r; Item v = a[r];
 	for (;;)
 	{ 
 		while (less(a[++i], v)) ;
 		while (less(v, a[--j])) if (j == l) break;
 		if (i >= j) break;
 		exch(a[i], a[j]);
 	}
 	exch(a[i], a[r]);
 	return i;
 }
 
 
 
/*非递归式的快速排序, 使用显式栈*/
#define push2(A, B)  push(B); push(A);
void quicksort(Item a[], int l, int r)
{ 
	int i;
	stackinit(); push2(l, r);
	while (!stackempty())
	{
		l = pop(); r = pop(); 
		if (r <= l) continue;
		i = partition(a, l, r);
		if (i-l > r-i)
			{ push2(l, i-1); push2(i+1, r); }
		else
			{ push2(i+1, r); push2(l, i-1); }
	}
}

/*三分取中划分 改进的快速算法*/

#define M 10
void quicksort(Item a[], int l, int r)
{ 
	int i; 
	if (r-l <= M) return;
	exch(a[(l+r)/2], a[r-1]);
	compexch(a[l], a[r-1]); 
	compexch(a[l], a[r]); 
	compexch(a[r-1], a[r]);
	i = partition(a, l+1, r-1);
	quicksort(a, l, i-1);
	quicksort(a, i+1, r);
} 
void sort(Item a[], int l, int r)
{ 
	quicksort(a, l, r);
	insertion(a, l, r);
}


/*三路划分的快速排序算法 适合于字符串的排序*/
#define eq(A, B) (!less(A, B) && !less(B, A))
void quicksort(Item a[], int l, int r)
{ 
	int i, j, k, p, q; Item v;
	if (r <= l) return;
	v = a[r]; i = l-1; j = r; p = l-1; q = r;
	for (;;)
	{ 
		while (less(a[++i], v)) ;
		while (less(v, a[--j])) if (j == l) break;
		if (i >= j) break;
		exch(a[i], a[j]);
		if (eq(a[i], v)) { p++; exch(a[p], a[i]); }
		if (eq(v, a[j])) { q--; exch(a[q], a[j]); }
	}
	exch(a[i], a[r]); j = i-1; i = i+1;
	for (k = l  ; k < p; k++, j--) {
		exch(a[k], a[j]);
	}
	for (k = r-1; k > q; k--, i++) {
		exch(a[k], a[i]);
	}
	quicksort(a, l, j);
	quicksort(a, i, r); 
}


/* 基于快速排序的选择算法 */
select(Item a[], int l, int r, int k)
{ 
	int i;
	if (r <= l) return;
	i = partition(a, l, r);
	if (i > k) select(a, l, i-1, k);
	if (i < k) select(a, i+1, r, k);
}
/* 基于快速排序的非递归选择算法 */
select(Item a[], int l, int r, int k)
{ 
	while (r > l)
	{ 
		int i = partition(a, l, r);
		if (i >= k) r = i-1;
		if (i <= k) l = i+1;
	} 
}