随机的快速排序算法
仅仅在原来的快速排序基础上增加了取随机数为划分点，改进了原有快排使用第一个元素作为划分元素的缺点，即减少了遇到最坏情况的可能。
-
#include<iostream>
-
#include<time.h>
-
using namespace std;
-
-
#define N 20 // 最大数组个数
-
-
#define MULTIPLIER 0x015A4E35L
-
#define INCREMENT 1
-
-
static unsigned long seed;
-
-
/* 生成随机数种子 */
-
void random_seed(unsigned long d){
-
if(d==0){
-
seed = time(0);
-
}else{
-
seed = d;
-
}
-
}
-
-
/* 生成一个low~high范围内的随机数 */
-
unsigned int random(unsigned long low, unsigned long high){
-
seed = MULTIPLIER * seed + INCREMENT;
-
return ((seed>>16)%(high-low)+low);
-
}
-
-
/*
-
* 按枢点元素划分序列
-
* 输入：数组A[]，序列的起始位置low，终止位置high
-
* 输出：按枢点元素划分的序列A[]，枢点元素位置i
-
*/
-
template<class Type>
-
int split(Type A[], int low, int high){
-
int k, i = low;
-
Type x= A[low];
-
for(k = low+1; k<=high; k++) {
-
if(A[k]<=x){
-
i ++;
-
if(i!=k){
-
swap(A[i], A[k]);
-
}
-
}
-
}
-
swap(A[low], A[i]);
-
return i;
-
}
-
-
/*
-
* 初始化随机数并执行快排
-
* 输入：数组A[]，序列的起始位置low，终止位置high
-
* 输出：排序好的序列A[]
-
*/
-
template<class Type>
-
void quicksort_random(Type A[], int low, int high){
-
random_seed(0);
-
r_quicksort(A, low, high);
-
}
-
-
/*
-
* 随机选择枢点的快速排序
-
* 输入：数组A[]，序列的起始位置low，终止位置high
-
* 输出：排序好的序列A[]
-
*/
-
template<class Type>
-
void r_quicksort(Type A[], int low, int high){
-
int k;
-
if( low < high ){
-
k = random(low, high);
-
swap(A[low], A[k]);
-
k = split(A, low, high);
-
r_quicksort(A, low, k-1);
-
r_quicksort(A, k+1, high);
-
}
-
}
-
-
int main(){
-
int A[N];
-
int i, n;
-
-
cin>>n;
-
-
for(i=0; i<n; i++)cin>>A[i];
-
-
quicksort_random(A,0,n-1);
-
-
for(i=0; i<n-1; i++)cout<<A[i]<<" ";
-
cout<<A[n-1]<<endl;
-
-
return 0;
-
}
