学步园

刚刚复习完快速排序。实现了一个简单的快速排序，其中还有不少地方可以优化：

1. 三点中值法，在选择三个值并取中间值作为桩。

2. 在元素个数较少时，直接使用插入排序。

突然想起来看看STL中的sort函数是怎样实现的，发现其也使用了这几种优化方法。并结合了堆排序。

下面是我实现的一个简单的STL中的sort，叫做introsort

#include <iostream>
#include "heapsort.cpp"
using namespace std;

#define STL_THRESHOLD 16	//阙值，STL中取16

//三点中值，取三个数，中间大小的
inline const int& median(const int& a, const int& b, const int& c)
{
	if(a < b)
	{
		if(b < c) return b;
		else if(c < a) return a;
		else return c;
	}
	else
	{
		if(b > c) return b;
		else if(a > c) return c;
		else return a;
	}
}

//交换函数
inline void swap(int *A, const int a, const int b)
{
	int tmp = A[a];
	A[a] = A[b];
	A[b] = tmp;
}

//控制分支恶化，找出最大的k使得2^k<n。
inline int lg(int n)
{
	int k;
	for(k = 0; n > 1; n >>= 1) k++;
	return k;
}

//快速排序中的划分函数，使用三点中值法来提高效率
int partition(int *A, int start, int end, int key)
{
	while (true)
	{
 		while (A[start] < key) start++;
		while (A[end] > key) end--;
		if(start >= end)
			return start;
		swap(A, start, end);
		start++;
	}
}

//introsort基本和快速排序相同，只是加入了阙值停止排序，并在分支恶化比较严重时使用堆排序进行子序列的排序
void introsort(int *A, int start, int end, int depth_limit)
{
	while ((end - start) > STL_THRESHOLD)	//长度大于阙值，继续使用快排
	{
		if(depth_limit == 0)	//深度过深，恶化严重，使用堆排序
		{
			heapsort(A, end - start + 1);
			return;
		}
		depth_limit--;
		int tmp = partition(A, start, end, median(A[start], A[start + (start + end)/2], A[end]));
		introsort(A, start, tmp - 1, depth_limit);
		introsort(A, tmp + 1, end, depth_limit);
	}
}



//插入排序
void insertion_sort(int *A, int start, int end)
{
	for(int i = start + 1; i <= end; i++)
	{
		int j = i - 1;
		while (A[j] > A[j + 1] && j >= start)
		{
			swap(A, j, j + 1);
			j--;
		}
	}
}


inline void sort(int *A, int start, int end)
{
	//先使用introsort，当子序列长度小于阙值时，停止排序，这时数组基本有序，再使用插入排序完成剩下的排序
	if(start < end)
	{
		introsort(A, start, end, lg(2 * (end - start)));
		insertion_sort(A, start, end);
	}
}



int main()
{
	int A[10] = {10, 5, 1, 8, 4, 2, 6, 12, 7, 2};
	sort(A, 0, 9);
	for(int i=0;i<10;i++)
		cout<<A[i]<<" ";
}

其实还有很多地方可以优化，比如在快速排序时使用多线程来帮助分区。