快速排序

通过分而治之实现nlog(n)的排序算法

c++实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template<typename T>
void quick_sort(vector<T> arr, int start, int end){
	if(start >= end) return;
	T mid = arr[start];
	int left = start, right = end;
	while(left < right) {
		while(arr[right] >= mid && left < right) --right;
        while(arr[left] <= mid && left < right) ++left;
		std::swap(arr[left], arr[right]);
	}
	
	std::swap(arr[left], arr[start]);
    
	quick_sort(arr, start, left-1);
	quick_sort(arr, right+1, end);
}

这里–right和++left是不能够交换顺序的，每次循环结束left==right，这是确保arr[right]一定小于mid（当然在元素全部一样的情况下都等于mid）

为什么一定要有这个保证呢？因为我们是递归实现的，每次递归数组长度应该在缩减，也就是left-1和right+1，而此时中间值就必须是mid才不会出错