每次寫快速排序都會(huì)遇到很多的坑，基本不會(huì)一次性寫對，以后每次寫一次免胃，都將遇到的坑記錄在此音五。
代碼如下：
template<class Iter>
void quick_sort(Iter begin, Iter end) {
int sz = (int)distance(begin, end);
if (sz < 2) return;
//保存現(xiàn)場；
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);
}
第一羔沙，等于的時(shí)候進(jìn)不進(jìn)行交換躺涝。
需要進(jìn)行交換，理由就是盡量使得被target被交換到數(shù)組的中央扼雏；
問題就出現(xiàn)了坚嗜，如何保證等于的時(shí)候，不會(huì)發(fā)生死循環(huán)诗充；
while (*--e > tmp); //這里沒有等號(hào)苍蔬；比較的時(shí)候先--了，就避免了重復(fù)元素蝴蜓；
while (b < e && *++b < tmp);
第二碟绑，從頭遍歷還是從后遍歷。
從后遍歷茎匠，因?yàn)榈谝稽c(diǎn)等于的時(shí)候也要進(jìn)行交換格仲，所以向后遍歷最差情況也只是到第一個(gè)元素的時(shí)候停止，此時(shí)遍歷的過程中是不需要加上while(i < j)的判斷的诵冒；
while (*--e > tmp); //這里不需要檢驗(yàn)b < e凯肋；
while (b < e && *++b < tmp); //這里必須檢驗(yàn)；
第三造烁，循環(huán)外與begin交換的是b否过，還是e午笛。
這里是e惭蟋，注意主要經(jīng)過while (b < e)循環(huán)，e最后的位置一定保證是*begin最終的位置药磺。
每次都必須經(jīng)過這個(gè)循環(huán)告组，才能保證iter_swap(begin, e)；的正確性癌佩，所以b要從begin開始木缝，e要從end開始，而不是分別從begin+1围辙，end - 1開始我碟，會(huì)導(dǎo)致兩個(gè)元素的時(shí)候，沒有經(jīng)過while循環(huán)就直接進(jìn)行與*begin的交換姚建，導(dǎo)致錯(cuò)誤矫俺。
第四，可以將第三個(gè)while的b < e也去掉不。
可以厘托，只要保證target（*begin）元素是中間值就好了友雳，將中間元素，最后的元素和第一個(gè)元素這三個(gè)值重新分配一下順序铅匹，使得其按中間值押赊，最小值，最大值的順序重新排列包斑，這樣就可以保證左右都可以不用檢驗(yàn)了流礁；
此時(shí)也可以從開頭來遍歷，但是最終位置舰始，就是后遍歷的那一個(gè)崇棠。
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); //因?yàn)楹蟊闅v且沒有檢驗(yàn)，所以end是最后的值丸卷。
if (begin < end) std::iter_swap(begin, end);
}
std::swap(*it1, *end); //*it只會(huì)在這里改變枕稀，所以無需使用臨時(shí)值；
quick_sort3(it1, end);
quick_sort3(std::next(end), it2);
}
第五谜嫉，考慮比較函數(shù)的話萎坷，如何使用cmp的問題；
stl中的存在比較函數(shù)的sort函數(shù)與不存在比較函數(shù)的sort函數(shù)是重載的關(guān)系沐兰，不是使用默認(rèn)參數(shù)來實(shí)現(xiàn)的哆档；（感覺模板的默認(rèn)參數(shù)十分不靠譜，好像不能有默認(rèn)參數(shù)住闯，模板類可以有瓜浸，但是模板函數(shù)的默認(rèn)參數(shù)不可以）
問題在cmp默認(rèn)是less<T>，兩個(gè)參數(shù)t1,t2比原，只有t1 < t2時(shí)才返回true插佛，所以要考慮等于的時(shí)候，可以使用如下方法轉(zhuǎn)化量窘，先寫出<號(hào)的版本雇寇，如果是大于號(hào)，就將兩個(gè)變量轉(zhuǎn)換一下位置蚌铜。最后锨侯，直接將<替換為cmp函數(shù)即可。
while (*--e > tmp);
while (b < e && *++b < tmp);
轉(zhuǎn)換一下：
while (tmp < *--e);
while (b < e && *++b < tmp);
然后進(jìn)行替換：
while (cmp(tmp, *--e));
while (b < e && cmp(*++b, tmp));
