#include <iostream>

 using namespace std;

 //交换数据

 void Swap(int array[], int i, int j)

 {

     int temp = array[i];

     array[i] = array[j];

     array[j] = temp;

  }

 //选择问题,index 表示选择第i个最小元素

 int RandomSelect(int array[], int size, int index)

 {

     if (size <=)

     {

         return array[size-];   //只有一个元素时即为需要选择的元素

     }

     int key = ;

     Swap(array, , rand()%size);  //随机化取样，获得关键值key并与array[0]交换

     //进行区域划分,分别与key比较，小于key的都在左边，大于key的都在右边

     for (int i=; i<size; ++i)

     {

         if (array[i] < array[])

         {

             Swap(array, ++key, i);

         }

     }

     Swap(array, , key);//关键值key回到正确的位置

     if (key == index-) //相等，即为需要选择的第i个元素

     {

         return array[key];

     }

     else if (index- < key) //index小于key，即第i个元素在划分区域的左边

     {

         return RandomSelect(array, key, index);

     }

     else//index大于key，即第i个元素在划分区域的左边，注意同时更新index-key-1（去除key本身）

     {

         return RandomSelect(array+key+, size-key-, index-key-);

     }

 }

 void main()

 {

     int Array[] = {, , , , , , , , , };

     int i = ;

     cout << "第" << i <<"个最小元素: "

          << RandomSelect(Array, , i) << endl;

     system("pause");

 }