这个算是捏软柿子了哇。
不过用模板来实现也是非常有趣。
快排的核心就是：
1、在数组中选择一个参考值X，再设置2个索引，一个用来记录比这个X小的位置i，一个用来记录比这个X大的位置j
2、比如是升序排序，就把大的值交换到小的值的位置，小的值交换到大的值的位置，如果是降序，就相反的交换，总而言之，就是交换一下值
3、如果没有找到满足比较条件的值，比如升序，没有找到比参考值X小的值，就将索引j加1，继续找，找到了，就将小的值的索引i加1，然后交换
4、如此，到循环结束，比如升序，将最后索引i所在位置的值与X所在位置的值交换，这个i就把数组分开成2半了，然后对左右的2半进行同样如上几步操作，即递归完成了排序。
所以参考值X的选择非常重要，运气差的话，就分不均匀，可能达到O（n^2）的复杂度了，也就出现随机分断的版本，这是看人品嘛。
补充了尾递归的实现。
下面是俺的练手之作：
1 #include <iostream>
2 #include <vector>
3 #include <functional>
4 #include <cassert>
5 #include <cmath>
6 #include <ctime>
7 #include <cstdlib>
8 #include <random>
9
10 using namespace std;
11
12 template<typename _InIt, typename _Func>
13 _InIt __partition(_InIt first, _InIt last, _Func& Func) {
14 typedef typename iterator_traits<_InIt>::value_type _ValueType;
15
16 _ValueType val = *(last);
17 _InIt _Ite = first-1;
18
19 for (_InIt it = first; (last-it)>=1; ++it) {
20 if (Func(*it, val)) {
21 _Ite++;
22 iter_swap(_Ite, it);
23 }
24 }
25
26 iter_swap(++_Ite, last);
27 return _Ite;
28 }
29
30 template<typename _InIt, typename _Func>
31 _InIt randomized_partition(_InIt first, _InIt last, _Func& Func) {
32 size_t offset = last - first;
33 assert((last - first)>0);
34
35 random_device rd ;
36 default_random_engine e(rd());
37 uniform_int_distribution <> u(0, offset);
38
39 iter_swap(last, first+u(e));
40 return __partition(first, last, Func);
41 }
42
43 template<typename _InIt, typename _Func>
44 void __quick_sort(_InIt first, _InIt last, _Func& Func) {
45 if (last - first > 0) {
46 _InIt it = randomized_partition(first, last, Func);
47 __quick_sort(first, it-1, Func);
48 __quick_sort(it+1, last, Func);
49 }
50 }
51
52 template<typename _InIt, typename _Func>
53 void quick_sort(_InIt first, _InIt last, _Func& Func) {
54 __quick_sort(first, --last, Func);
55 }
56
57 int main() {
58 int lst[] = {2,8,7,1,3,5,6,4};
59 vector<int> v(lst, lst+8);
60
61 //greater_equal<int> cmp;
62 less_equal<int> cmp;
63 quick_sort(v.begin(), v.end(), cmp);
64
65 for(vector<int>::iterator it=v.begin(); it != v.end(); it++)
66 cout << *it << " ";
67 cout << endl;
68
69 return 0;
70 }
这里补充一个模拟尾递归的实现（可以说是迭代啦）：
1 template<typename _InIt, typename _Func>
2 void tail_rescursive_quick_sort(_InIt first, _InIt last, _Func& Func) {
3 while (last - first > 0) {
4 _InIt it = __partition(first, last, Func);
5 tail_rescursive_quick_sort(first, it-1, Func);
6 first = it + 1;
7 }
8 }
对于上面的quick_sort，它的区别在于通过循环不断将数组从左边向右边逼近，每次不用开启更多的函数调用栈，可以避免过度递归调用栈溢出。
可以形象的想象上面非尾递归它的栈就像一个二叉树（坏的情况下是一个完全平衡的二叉树的话），随着树的高度越高会比尾递归的栈多出非常多。
参考C++11的随机数：
http://www.cnblogs.com/egmkang/archive/2012/09/06/2673253.html