每日算法：快速排序

要求：

手撕快排，用于个人复习。

这玩意隔一段时间不写就容易出错，警钟长鸣。

出错点：

（1）返回值类型是 void ，可不可以是 vector<int> ？

（2）如果是void，传入参数的 vector 就要写成引用；

（3）最外层是 while(left < right) ， 内层也是 while(left < right) ，因为在大while中的每轮循环都有可能导致 left >= right ；

（3）交换数据时，不是 swap() 而是赋值，因为交换数据的条件是单方面的（left 指针找到比 pivot 大的或者 right 指针找到比 pivot 小的），如果两边都比 pivot 大 或者都比 pivot 小，就会导致永远在重复 swap()；

（4）递归时的边界是 left - 1 和 right + 1，因为一轮排序结束时 left == right 且 arr[left] == arr[right] == pivot ，pivot已经没必要加入下一轮排序了。

代码：（懒得写注释了）

// 快速排序
#include <iostream>
#include <vector>

using namespace std;

void quickSort(vector<int>& arr, int begin, int end) {
	if (begin >= end) {
		return;
	}
	int pivot = arr[begin];
	int left = begin;
	int right = end;
	while (left < right) {
		while (left < right && arr[right] >= pivot) {
			--right;
		}
		// 此处判断是重点
		if (left < right) {
			arr[left] = arr[right];
		}
		while (left < right && arr[left] <= pivot) {
			++left;
		}
		if (left < right) {
			arr[right] = arr[left];
		}
	}
	arr[left] = pivot;
	quickSort(arr, begin, left - 1);
	quickSort(arr, right + 1, end);
}

int main() {
	vector<int> v = {1, 1, 4, 5, 1, 4, 1, 9, 1, 9, 8, 1, 0};
	quickSort(v, 0, 12);
	for (auto info : v) {
		cout << info << " ";
	}
	cout << endl;
	return 0;
}