#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;

}

 

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