快速排序遇到的坑

每次写快速排序都会遇到很多的坑，基本不会一次性写对，以后每次写一次，都将遇到的坑记录在此。

代码如下：

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));