【機械試験練習】【C++】ランダム選択アルゴリズム

/*
	          
*/
#include
#include
#include
#include
#include

using namespace std;

//        :       ， A left right      
int randPartition(int A[], int left, int right){
	int p = round(1.0 * rand() / RAND_MAX * (right - left) + left);
	swap(A[p], A[left]);
	int temp = A[left];
	while(left < right){
		while(left < right && A[right] > temp) right --;
		A[left] = A[right];
		while(left < right && A[left] <= temp) left ++;
		A[right] = A[left];
	}
	A[left] = temp;
	return left;
}

int startRandSelect(int A[], int left, int right, int K){
	if(left == right) return A[left];
	int p = randPartition(A, left, right);
	int M = p - left + 1; //       M 
	if(M == K){
		return A[p];
	} else if(K < M){
		return startRandSelect(A, left, p - 1, K);
	} else {
		return startRandSelect(A, p + 1, right, K - M);
	}
}

//  A    K    
int randSelect(int A[], int left, int right, int K){
	srand((unsigned)time(NULL));
	return startRandSelect(A, left, right, K);
} 
 
int main(){
	int m[5] = {3,424 ,54 ,23, 1};
	printf("%d", randSelect(m, 0, 4, 7));
	return 0;
}