随机快速排序C++实现

传统的随机快速排序，是选定一个数，然后以这个数为标杆，分为小于等于（标杆）区和大于（标杆）区。

改进的快速排序，分为，小于区，等于区和大于区。这个划分的过程用partition函数实现。

具体请看代码。

#ifndef QUICKSORT_H
#define QUICKSORT_H
#include<iostream>
#include<vector>
#include<ctime>
using namespace std;
void swap(vector<int>&arr, int i, int j)
{
	int temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
}
vector<int> partition(vector<int> &arr,  int l, int r)
{
	
	int less = l - 1;//less为小于区边界，也就是等于区的开头
	int more = r;//more为大于区边界，等于区的末尾
	while (l < more)
	{
		if (arr[l] < arr[r])//当前数小于划分值
		{
			swap(arr, ++less, l++);//交换当前数与小于区边界
		}
		else if (arr[l] > arr[r])//当前数大于划分值
			swap(arr, l, --more);//交换当前数和大于区边界
		else
			++l;//当前数与划分值相等，啥也不干，往下看下一个数。
	}
	swap(arr, more, r);//当l与more遇上了，则把划分值和大于区的边界交换回来
	vector<int>p{less+1,more};//返回等于区的边界
	return p;
}

void quickSort(vector<int>&arr, int l, int r)
{
	if (l < r)
	{
		srand((int)time(NULL));
		swap(arr, r, l+rand() % (r-l+1));//先随机选这一个数，与末尾数字交换
		vector<int>help = partition(arr, l, r);
		quickSort(arr, l, help[0] - 1);
		quickSort(arr, help[1] + 1, r);
	}
	
}
void quickSort(vector<int>&a)
{
	if (a.size() < 2)
		return;
	quickSort(a, 0, a.size() - 1);
}
#endif

int main()
{
	vector<int>a{ 1,2,3,4,5,10,9,8,7,6 };
	quickSort(a);
	for (auto c : a)
		cout << c << " ";
	system("pause");
	return 0;
}