快速排序——C++實作

快速排序

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