每次写快速排序都会遇到很多的坑，基本不会一次性写对，以后每次写一次，都将遇到的坑记录在此。
代码如下：
template<class Iter>
void quick_sort(Iter begin, Iter end) {
int sz = (int)distance(begin, end);
if (sz < 2) return;
//保存现场；
Iter b = begin ;
Iter e = end;
int tmp = *begin;
while (b < e) {
while (*--e > tmp);
while (b < e && *++b < tmp);
if (b < e)
iter_swap(b, e);
}
iter_swap(begin, e);
quick_sort(begin, e);
quick_sort(e + 1, end);
}
第一，等于的时候进不进行交换。
需要进行交换，理由就是尽量使得被target被交换到数组的中央；
问题就出现了，如何保证等于的时候，不会发生死循环；
while (*--e > tmp); //这里没有等号；比较的时候先--了，就避免了重复元素；
while (b < e && *++b < tmp);
第二，从头遍历还是从后遍历。
从后遍历，因为第一点等于的时候也要进行交换，所以向后遍历最差情况也只是到第一个元素的时候停止，此时遍历的过程中是不需要加上while(i < j)的判断的；
while (*--e > tmp); //这里不需要检验b < e；
while (b < e && *++b < tmp); //这里必须检验；
第三，循环外与begin交换的是b，还是e。
这里是e，注意主要经过while (b < e)循环，e最后的位置一定保证是*begin最终的位置。
每次都必须经过这个循环，才能保证iter_swap(begin, e)；的正确性，所以b要从begin开始，e要从end开始，而不是分别从begin+1，end - 1开始，会导致两个元素的时候，没有经过while循环就直接进行与*begin的交换，导致错误。
第四，可以将第三个while的b < e也去掉不。
可以，只要保证target（*begin）元素是中间值就好了，将中间元素，最后的元素和第一个元素这三个值重新分配一下顺序，使得其按中间值，最小值，最大值的顺序重新排列，这样就可以保证左右都可以不用检验了；
此时也可以从开头来遍历，但是最终位置，就是后遍历的那一个。
template<class Iter>
void median(Iter a, Iter b, Iter c) {
typedef typename Iter::value_type T;
if (b == c) {
if (*a > *b) std::swap(*a, *b);
return;
}
T max_element = std::max(std::max(*a, *b), *c);
T min_element = std::min(std::min(*a, *b), *c);
T mid = *a + *b + *c - max_element - min_element;
std::swap(*a, mid);
std::swap(*b, min_element);
std::swap(*c, max_element);
}
template<class Iter>
void quick_sort3(Iter it1, Iter it2) {
auto size = std::distance(it1, it2);
if (size <= 1) return;
median(it1, std::next(it1, size / 2), std::prev(it2));
Iter begin = it1;
Iter end = it2;
while (begin < end) {
while (*++begin < *it1);
while (*--end > *it1); //因为后遍历且没有检验，所以end是最后的值。
if (begin < end) std::iter_swap(begin, end);
}
std::swap(*it1, *end); //*it只会在这里改变，所以无需使用临时值；
quick_sort3(it1, end);
quick_sort3(std::next(end), it2);
}
第五，考虑比较函数的话，如何使用cmp的问题；
stl中的存在比较函数的sort函数与不存在比较函数的sort函数是重载的关系，不是使用默认参数来实现的；（感觉模板的默认参数十分不靠谱，好像不能有默认参数，模板类可以有，但是模板函数的默认参数不可以）
问题在cmp默认是less<T>，两个参数t1,t2，只有t1 < t2时才返回true，所以要考虑等于的时候，可以使用如下方法转化，先写出<号的版本，如果是大于号，就将两个变量转换一下位置。最后，直接将<替换为cmp函数即可。
while (*--e > tmp);
while (b < e && *++b < tmp);
转换一下：
while (tmp < *--e);
while (b < e && *++b < tmp);
然后进行替换：
while (cmp(tmp, *--e));
while (b < e && cmp(*++b, tmp));
