ランダムセレクトアルゴリズム

問題の説明:
本論文では,無秩序な配列からk番目に大きい数をどのように求めるかという問題を主に論じた.この問題の最も直接的な考え方は,配列を並べてk番目の要素を直接取り出すことであり,O(nlogn)の時間的複雑さが必要である.(この方法は比較的簡単で、実行時間が許容される場合はもちろんこの方法を選択する)ランダム選択アルゴリズムを紹介し、任意の入力に対してO(n)の所望の時間複雑度を達成することができる.
基本思想:ランダム選択アルゴリズムの原理はランダム高速ソートアルゴリズムに似ている.A[left,right]に対してrandPartition関数を1回実行すると、マスターの左側の要素の数が決定され、マスターよりも小さくなります.このとき主元がA[p]であると仮定すると、A[p]はA[left,right]の最初のp-left+1の大きな数である.Mにp-left+1を表すようにしてもよいが、k=Mが成立すれば、k番目に大きい数が主元A[p]であることを示す.kの場合

void randSelect(int n[], int left, int right,int k){
    if (left == right) return;
    int p = randPartition(n, left, right);
    int m = p - left + 1;
    if (k == m) return;
    if (k

ランダム選択アルゴリズムの最悪の時間複雑度はO(n)であるが²),しかし,任意の入力に対する所望時間の複雑さはO(n)であり,このアルゴリズムを最悪にする特定のデータのセットが存在しないことを意味し,かなり実用的で優れたアルゴリズムである.
ps:ランダムクイックソートアルゴリズムクリックでリンクを開く
適用:
整数からなる集合が与えられ、集合中の整数はそれぞれ異なり、2つのサブ集合が元の集合となるように2つのサブ集合に分割され、空に交差するとともに、2つのサブ集合の要素個数n 1とn 2の差の絶対値ができるだけ小さい場合、それぞれの要素の和S 1とS 2の差の絶対値ができるだけ大きくなる.|S 1-S 2|の値を求めます.

#include
#include
#include
#include
#include
using namespace std;
//      ，   [left,right]    
int randPartition(int n[], int left, int right){
    //  [left,right]     p
    int p = round(rand() / RAND_MAX*(right - left) + left);
    swap(n[p], n[left]);    //  n[p],n[left]；swap      algorithm 
    //     （    ）  Partition       
    int temp = n[left];     // n[left]       temp 
    while (lefttemp) right--;      
        n[left] = n[right];
        while (left < right&&n[left] <= temp) left++;
        n[right] = n[left];
    }
    n[left] = temp;         // temp  left right     
    return left;            //      
}
//      ， n[left,right]    k   ，     
void randSelect(int n[], int left, int right,int k){
    if (left == right) return;
    int p = randPartition(n, left, right);
    int m = p - left + 1;
    if (k == m) return;
    if (k