使用Java或C++等语言中内置的随机函数实现随机化快速排序，在数组中随机选择一个元素作为分区的主元(Pivot)。 输入 多组样例输入，每组由一个一维整型数组组成。 输出 随机化快速排序之后的一维整型数组（升序排列）。 样例输入 Copy 6 1 8 6 5 3 4 5 12 42 2 5 8 样例输出 Copy 1 3 4 5 6 8 2 5 8 12 42
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void quicksort(int a[],int low,int high){
if(low>=high)return;
int flag=rand()%(high-low+1)+low;//随机化生成
int i=low,j=high;
swap(a[low],a[flag]);//仅仅是需要与第一个做交换就OK啦，这样就又变回了以第一个数作为交换
int key=a[low];
while(i<j){
while(a[j]>=key&&i<j)
j--;
while(a[i]<=key&&i<j)
i++;
if(i<j)
swap(a[i],a[j]);
}
a[low]=a[i];
a[i]=key;
quicksort(a,low,i-1);
quicksort(a,i+1,high);
}
int main(){
int n;
while(cin>>n){
int a[n];
for(int i=0;i<n;i++){
cin>>a[i];
}
quicksort(a,0,n-1);
for(int i=0;i<n;i++)
if(i!=n-1)
cout<<a[i]<<" ";
else cout<<a[i]<<endl;
}
return 0;
}
