先上代碼：（時間復雜度后面分析＞＿＜）
#include<iostream>
#include<stdio.h>#include<stdlib.h>#include<time.h>using namespace std;void exchange(int *a,int *b){ if(a!=b) { int t=*a; *a=*b; *b=t; }}int partition(int *a,int left,int right){int x=a[right];int i=left-1;int j=left;for(;j<right;++j) { if(a[j]>=x) { ++i; exchange(&a[i],&a[j]); } } exchange(&a[i+1],&a[right]); return i+1;}int randomized_partition(int *a,int left,int right){srand((int)time(0));int i=rand()%(right-left+1)+left;if(i!=right)exchange(&a[i],&a[right]);return partition(a,left,right);}int Randomized_Select(int *a,int left,int right,int k){if(left==right) return a[left];int q=randomized_partition(a,left,right);int key=q-left+1;if(key==k)return a[q];else if(k<key)return Randomized_Select(a,left,q-1,k);elsereturn Randomized_Select(a,q+1,right,k-key);}int main(){int a[10]={1,9,2,8,10,3,4,7,6,5};int k;cin>>k;int k_max=Randomized_Select(a,0,9,k);cout<<k<<" Max: "<<k_max<<endl;return 0;}期望為線性時間的選擇算法
時間復雜度：
新聞熱點
疑難解答
