算法导论第2版 9.2 线性时间做选择

本文主要是介绍算法导论第2版 9.2 线性时间做选择，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

以书上伪代码为模板编写

#include<iostream>
using namespace std;
int A[11] = {-1,4,1,8,3,10,2,5,6,9,7};//下标从1开始,因此A[0]不用,用-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);//调用划分函数
}int randomized_select(int *A, int p,int r, int i)
{if(p == r)return A[p];int q = randomized_partition(A, p, r);//随机划分,q为pivot int k = q-p+1;//计算包括A[q]在内的左半边长度 if(i == k)//A[q]左边的元素都比它小,因此A[q]是第q-p+1(即k)小的元素 return A[q];else if(i < k) return randomized_select(A, p, q-1, i);//i<k时,找A[p...q-1]中第i小 elsereturn randomized_select(A, q+1, r, i-k);//i>k时,找A[q+1...r中第i-k小 
} int main()
{int i = randomized_select(A, 1, 10, 6);cout<<i;
}