#include<iostream>
#include <vector>
#include <cstdlib>
#include<ctime>
using namespace std;
/*
作用：返回一个在（min,max）之间的一个随机整数
参数：min--返回值的最小限制
max--返回值的最大限制
*/
int random(int min,int max)
{
srand((unsigned)time(NULL));//设置随机数的来源
return rand()%(max-min+1)+min;

}

/*
作用：将数组r位置的数据移动到相应的位置,
使得其左边的元素都小于数组r,右边的元素都大于r;
参数：A--需要操作的数组
P--操作数组的起始位置（不一定是数组的首个元素）
R--操作数组的终止位置（不一定是数组的终止元素）
返回值：原数组R的最后位置
说明：由于使用的容器，为值传递,需要传递地址
*/

int Partition(vector<int> &A, int p, int r)
{
int x = A[r];
int i = p - 1;
int flag;
for (int j = p; j <= (r - 1); j++)
{
if (A[j]<=x)
{
i = i + 1; //记录最后元素需要移动的位置
flag = A[i]; //将A[i]与A[j]进行交换
A[i] = A[j];
A[j] = flag;
}
}
flag = A[i+1]; //将数组R插入到相应的的地方
A[i+1] = A[r];
A[r] = flag;
return (i + 1);
}
void QuitSort(vector<int> &A, int p, int r)
{
int q;
if (p < r)
{
q = Partition(A, p , r);
QuitSort(A, p, q - 1);
QuitSort(A, q + 1, r);

}
}
/*
为了弥补快速排序的分配不均，对最后一个数据进行随机抽选
*/
int RandomPartition(vector<int> &A, int p, int r)
{
int i = random(p, r);
int flag = 0;
flag = A[i];
A[i] = A[r];
A[r] = flag;
return Partition(A, p, r);
}
void RandomQuitSort(vector<int> &A, int p, int r)
{
int q;
if (p < r)
{
q = RandomPartition(A, p, r);
RandomQuitSort(A, p, q - 1);
RandomQuitSort(A, q + 1, r);

}
}

int main()
{
vector<int> A({2,8,7,1,3,5,6,4});
vector<int>::iterator i = A.begin ();
int j = 0;
int q = 0;
QuitSort(A, 0, A.size() - 1);
for (j = 0; j < A.size(); j++)
{
cout << A[j] << endl;

}
RandomQuitSort(A, 0, A.size() - 1);
for (j = 0; j < A.size(); j++)
{
cout << A[j] << endl;

}
cin >> j;
}

//若发现代码有所问题，希望与我联系，本人感激不尽

随机快速排序