4.3 快速排序的随机化版本

      这种方法并不是一种全新的排序算法，而是在快速排序的基础上加入随机化的因素，因素，因而仍然将其作为第四种方法（快速排序）的一种补充。

      为什么要提出快速排序的随机化版本，主要是对于快速排序法其划分情况的好坏会直接影响排序的效率，而且，快速排序的平均性能较好，所以，加入随机化成分，可以使该算法对于所有输入均能获得较好的平均情况性能。

      针对加入随机化的环节，选取的是选取主元的环节，因为主元的选取直接影响快速排序算法的数组划分。

C代码实现为：

#include <stdio.h>
#include <random>
//交换两数
void exchange(int &a, int &b) {
	if(a!=b) {
		int temp = a;
		a = b;
		b = temp;
	}
}
//数组划分
int portition(int a[], const int &start, const int &end){
	int x = a[end];
	int i = start;
	for(int j=start; j<end; j++) {
		if( x>a[j] ) {
			exchange(a[i], a[j]);
			i = i+1;
		}
	}
	exchange(a[i], a[end]);
	return i;
}
//随机选取主元
int  random_portition(int a[], const int &start, const int &end) {
	int indexRandom = rand()%(end-start+1) + start;
	exchange(a[indexRandom], a[end]);
	return portition(a, start, end);
}
//快速排序的随机化版本
void random_quicksort(int a[], const int &start, const int &end){
	if( start<end ) {
		int mid = random_portition(a, start, end);
		if(mid!=0) {
			random_quicksort(a, start, mid-1);
		}
		random_quicksort(a, mid+1, end);
	}
}

int main(int argc, char** argv) {
	const int length = 25;
	int a[length];
	for(int i=0; i<length; i++){
		a[i] = rand()%100;
	}
	for(int i=0; i<length; i++) {
		printf("%d ", a[i]);
	}
	printf("\n");
	random_quicksort(a, 0, length-1);
	for(int i=0; i<length; i++) {
		printf("%d ", a[i]);
	}
	printf("\n");
	return 0;
}

#include <random>
#include <iostream>
#include <vector>
using namespace std;

//交换两数位置
void exchange(int &a, int &b) {
	if(a!=b) {
		int temp = a;
		a = b;
		b = temp;
	}
}
//数组划分
vector<int>::iterator portition(vector<int> &aVec, const vector<int>::iterator &itStart, const vector<int>::iterator &itEnd) {
	int x = *(itEnd);
	vector<int>::iterator i = itStart;
	for(vector<int>::iterator j=itStart; j<itEnd; j++) {
		if( x>*(j) ) {
			exchange(*(i), *(j));
			i = i+1;
		}
	}
	exchange(*(i), *(itEnd));
	return i;
}
//选取随机的主元
vector<int>::iterator random_portition(vector<int> &aVec, const vector<int>::iterator &itStart, const vector<int>::iterator &itEnd) {
	vector<int>::iterator indexRandom = rand()%(itEnd-itStart+1) + itStart;
	exchange(*(indexRandom), *(itEnd));
	return portition(aVec, itStart, itEnd);
}
//快速排序的随机化版本
void random_quicksort(vector<int> &aVec, const vector<int>::iterator &itStart, const vector<int>::iterator &itEnd) {
	if( itStart<itEnd ) {
		vector<int>::iterator mid = random_portition(aVec, itStart, itEnd);
		if(mid!=itStart) {
			random_quicksort(aVec, itStart, mid-1);
		}
		random_quicksort(aVec, mid+1, itEnd);
	}
}

int main(int argc, char** argv) {
	vector<int> a;
	for(int i=0; i<20; i++){
		a.push_back( rand()%100 );
	}
	for(vector<int>::iterator it=a.begin(); it<a.end(); it++) {
		cout<<*(it)<<" ";
	}
	cout<<endl;
	random_quicksort(a, a.begin(), a.end()-1);
	for(vector<int>::iterator it=a.begin(); it<a.end(); it++) {
		cout<<*(it)<<" ";
	}
	cout<<endl;
	return 0;
}