快速排序
template_head.h
#include <iostream>
#include <vector>
#include "../head_file/template_head.h"
using namespace std;
void quick_sort()
{
cout << "Quick Sort!!!" << endl;
vector<int> list = { 8,9,1,7,2,3,5,4,6,0,11,9,8 };
quickSort(list.begin(), list.end(), greater_<int>{});
printList(list);
}
template <typename Iterator>
void quickSort(const Iterator& begin, const Iterator& end) {
quickSort(begin, end, less_<decltype(*begin)>{});
}
template <typename Iterator, typename Comparator>
void quickSort(const Iterator& begin, const Iterator& end, Comparator lessThan) {
if (begin + 2 >= end)
return;
Iterator pivot = swapLeftRight(begin, end, lessThan);
/*cout << "begin: " << *begin <<" pivot: " << *pivot <<" end: " << *(end-1) << endl;
cout << "quickSort: ";
printList(begin, end);*/
quickSort(begin, pivot, lessThan); // 这里pivot是end,在实际的最后一个元素的下一位
quickSort(pivot+1, end, lessThan);
}
template <typename Iterator, typename Comparator>
Iterator swapLeftRight(const Iterator& begin, const Iterator& end, Comparator lessThan) {
Iterator pivot = begin + (end - begin) / 2;
auto tmp = *pivot;
/*cout << "tmp: " << tmp << endl;
cout << "begin_list: ";*/
//printList(begin, end);
std::swap(*pivot, *(end - 1));
//cout << "swap pivot to end: ";
//printList(begin, end);
Iterator i = begin, j = end - 2;
while (true)
{
while (lessThan(*i, tmp)) i++; // 找到第一个比tmp小的值
while (!lessThan(*j, tmp)) j--; // 找到第一个比tmp大的值
if (i < j) {
std::swap(*i, *j); // 交换i,j元素
//printList(begin, end);
}
else {
break;
}
}
std::swap(*i, *(end - 1));
return i;
}