改进的快速排序法.cpp

C++Example实用的算法:包括枚举

/*改进的快速排序法*/
#include <iostream.h>
typedef int ELEM;
typedef int KEY;
#define key(X) (X)
inline void swap(ELEM& a, ELEM& b)
{
	ELEM temp = a;
	a = b;
	b = temp;
}

void inssort(ELEM* array, int n)
//一般的插入排序法
{ 
	for (int i=1; i<n; i++)          //插入第ｉ个元素
		for (int j=i; (j>0) && (key(array[j])<key(array[j-1])); j--)
			swap(array[j], array[j-1]);
}
const int THRESHOLD=3;
extern long count1;
int partition(ELEM* array, int l, int r, KEY pivot)
{
	do 
	{                // 向中央移动左右边界直至它们相遇
		while (key(array[++l]) < pivot); 
		　　　　　　　　// 向右移动左边届
			while (r && (key(array[--r]) > pivot)); 
			　　　　　　　　// 向左移动右边界
				swap(array[l], array[r]);       
			　　　　　　　　 // 交换两边的元素
	} while (l < r);                   
	　　　　// 左右边界相遇时停止
		swap(array[l], array[r]);          
	return l;           
	　　　　// 返回右边分区的第一个元素
}

int findpivot(ELEM* array, int i, int j)  
{ 
	return (i+j)/2; 　　
		　　　　//简单的确定轴值的方法
}

void qsort(ELEM* array, int i, int j) 
{
	if (j <= i) return; 
	　　　　 // 检查边界值否合理
		int pivotindex = findpivot(array, i, j);
	　　　　／／确定分区的轴值
		swap(array[pivotindex], array[j]);
	　　　　 // 将轴值放置在最后
		int k = partition(array, i-1, j, key(array[j]));
	　　　　／／数组分区
		swap(array[k], array[j]);  // 放回轴值
	if ((k-i) >= THRESHOLD) 
		　　　　//分区的长度大于特定值使用快速排序
		qsort(array, i, k-1);
	if ((j-k) >= THRESHOLD) 
		qsort(array, k+1, j);
}

void sort(ELEM* array, int listsize) 
{
	qsort(array, 0, listsize-1);
	　　　  //首先使用快速排序
		inssort(array, listsize);  
	　　　　//最后由插入排序做收尾工作
}