void InsertionSort(int * const begin, int * const end) {

     int i, j, key;

     for (i = ; i < begin - end; ++i) {

         key = *(begin + i);

         for (j = i - ; j >=  && (*(begin + j) > key); --j) {

             *(begin + j + ) = *(begin + j);

         }

         *(begin + j + ) = key;

     }

 }

 int Partition(int * const begin, int * const end, int x) {

     int i = -;

     for (int j = ; j < (end - begin); ++j) {

         if (*(begin + j) < x) {

             ++i;

             swap(*(begin + i), *(begin + j));

         }

         else if (*(begin + j) == x && j != (end - begin - )) {

             swap(*(begin + j), *(end - ));

             --j;

         }

     }

     ++i;

     swap(*(begin + i), *(end - ));

     return i;

 }

 //返回第k小的元素,要求输入元素互异，最坏情况下时间复杂度为线性

 int Select(int * const begin, int * const end, int k) {

     if (end - begin == )

         return *begin;

     int n = end - begin;

     int groupnum = n / ; //groupnum个组，每组五个数

     int medium[]; //因小于50000个数

     int i, j, t = groupnum;

     for (i = , j = ; t--; i += ) {

         InsertionSort(begin + i, begin + i + );

         medium[j++] = *(begin + i + );

     }

     if (n > (groupnum * )) {

         InsertionSort(begin + i, end);

         medium[j++] = *(begin + i + (end - begin - i) / );

     }

     int x = Select(medium, medium + j, (j + ) / );

     int m = Partition(begin, end, x) + ;

     if (m == k)

         return x;

     else if (m > k)

         return Select(begin, begin + m - , k);

     else

         return Select(begin + m, end, k - m);

 }