c++的快速排序

c++的快速排序

原理就是分治法，我猜大家应该都已经了解了，主要讲一下具体实现细节：

以第1次排序为例，首先以第1位作为标准值std，你可以想象把它挖出来了，这个槽是空的，然后：

1. 从右边开始，往左找，找到第1个小于等于std值的数p，把这个数放到空槽里（交换，现在j的位置是空槽）。左指针右移一步。

 

2. 从左边开始，往右找，找到第1个大于std值的数q，把这个值放到空槽里（交换，现在i的位置是空槽）。然后j往左前进一步。

 之后就是重复1,2这2个过程，直到i和j相遇，这个时候i（j）的位置就是空槽，把std的值放进去。这样就完成了第1次排序。然后以std的位置为分割，对左、右2部分再递归的 *** 作就好了。

cpp实现：

#include
#include
using namespace std;


void quick_sort(vector &s, int l, int r) {	
	if (l < r) {
		int i = l, j = r, x = s[l];
		while (i < j) {
			while (i < j && s[j] >= x) j--;
			if (i < j) s[i++] = s[j]; // s[i]=s[j], i++

			while (i < j && s[i] < x) i++;
			if (i < j) s[j--] = s[i];
		}
		s[i] = x; // i==j
		quick_sort(s, l, i - 1);
		quick_sort(s, i + 1, r);
	}		
}


int main() {
	vector nums{ 1,4,2,3,2,5,1 };	
	quick_sort(nums,0,nums.size()-1);
	for (int item : nums) cout << item << " ";

	return 0;
}