算法导论第2版 7.3 快速排序随机化版本

本文主要是介绍算法导论第2版 7.3 快速排序随机化版本，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

根据书上伪码编写:

#include <iostream>
#include <ctime>
using namespace std;int A[11] = {-1,4,1,8,3,10,2,5,6,9,7};//下标从1开始,因此A[0]不用,用-1标记
int n = sizeof(A)/sizeof(int)-1;int partition(int *A, int p, int r)//划分函数
{int x = A[r];int i = p-1;int temp;for(int j = p; j<=r-1; j++){if(A[j] <= x){i++;temp = A[i];A[i] = A[j];A[j] = temp;}}temp = A[i+1];A[i+1] = A[r];A[r] = temp;return i+1;
}int randomized_partition(int *A, int p, int r)//从A[p]~A[r]中随机选择pivot
{int temp;int i = rand()%(r-p) + p;//生成p到r之间的随机数//原理:对于任意整数r,p有:0 <= rand()%(r-p+1) <= r-p//于是:0+p <= rand()%(r-p+1)+p <= r-p+p//即:p <= rand()%(r-p+1)+p <= rtemp = A[r];A[r] = A[i];A[i] = temp;return partition(A, p, r);//调用划分函数
}void ramdomized_quicksort(int *A, int p, int r)//随机快速排序的主体函数
{if(p < r){int q = randomized_partition(A, p, r);//生成pivot,赋给qramdomized_quicksort(A, p, q-1);//分治法,递归调用自身ramdomized_quicksort(A, q+1, r);}
}int main()
{//根据系统时间设置随机数种子srand( (unsigned)time(NULL) );ramdomized_quicksort(A, 1, n);//对A[1...n]进行原地快排for(int i = 0; i<=n; i++)//输出cout << A[i] << " ";
}