[C++知识库]快速排序的函数模板方法实现（c++）

快速排序是比较常用的排序方法，算法的时间复杂度最好为O(nlogn)，最坏时能达到O(n2)，是一种不稳定的排序方法。

快排的基本思想
1.选取一个基准
2.将比它”小”的放在它前面，比他“大”的放在后面
3.递归处理基准位置前后的两个子区间

实现步骤
函数传入的是指向第一个元素的位置和指向最后一个元素的位置，还可以传入一个比较函数(compare)

1.选定一个基准值
我们选择中间位置的元素的值作为排序的基准值，然后将第一个指针指向开始位置，将第二个指针指向结束位置

2.比较基准值，将所有元素除去基准元素划分为前后两个子区间
每一次循环，我们从前往后找到一个比基准值大的元素，再从后向前找一个比基准值小的元素，如果第一个指针位置小于等于第二个指针位置，则交换元素值

持续进行上面的操作，直到第一个指针位置大于第二个指针位置，即所有元素都被遍历过。

3.递归处理
基准元素所在的位置已经是其应该在的位置i - 1，所以只需要继续处理start~j?和 i~end这两个区间的元素

#include <iostream>

// 比较函数
template <typename T>
bool cmp(const T& a, const T& b)
{
	return a < b;
}
// 数组应该传入数组大小，这里可以由end -start + 1计算出，所以传入end参数要计算正确，否则
// 可能出现越界
template<typename T>
void qsortT(T *a, int start, int end, bool compare(const T&, const T&)=cmp)
{
	int i = start;
	int j = end;
	// 这里取中间位置的数为第一个基准
	T privot = a[(end - start) / 2 + start];
	while (i <= j)
	{
		while (i <= j && compare(a[i], privot))
		{
			i++;
		}
		while (i <= j && compare(privot, a[j]))
		{
			j--;
		}
		if (i <= j)
		{
			std::swap(a[i++], a[j--]);
		}
	}
	if (i < end)
	{
		qsortT(a, i, end, compare);
	}
	if (j > start)
	{
		qsortT(a, start, j, compare);
	}
	return;
}

int main(int argc, int argv)
{
	int arrInt[10] = { 5,10,3,4,18,78,38,22,1 };
	qsortT<int>(arrInt, 0, sizeof(arrInt) / sizeof(int) - 1);
	for (int i = 0; i < sizeof(arrInt) / sizeof(int); i++)
	{
		std::cout << arrInt[i] << ",";
	}
	std::cout << std::endl;
	char arrChar[7] = { 'b', 'd', 'a', 'A', 'Z','J','j'};
	qsortT<char>(arrChar, 0, sizeof(arrChar) / sizeof(char) - 1);
	for (int i = 0; i < sizeof(arrChar) / sizeof(char); i++)
	{
		std::cout << arrChar[i] << ",";
	}
	std::cout << std::endl;
	return 0;
}

运行结果：

0,1,3,4,5,10,18,22,38,78,
A,J,Z,a,b,d,j,