学步园

题目：输入n个整数，输出其中最小的k个。例如输入1，2，3，4，5，6，7和8这8个数字，则最小的4个数字为1，2，3和4。本文思路来自这里http://blog.csdn.net/v_JULY_v/article/details/6403777，对其方法进行了修改，算法思路按照编程之美。

思路：类似快速排序的划分方法，N个数存储在数组S中，再从数组中随机选取一个数X把数组划分为Sa和Sb俩部分，Sa<=X<=Sb，如果要查找的k个元素小于Sa的元素个数，则返回Sa中较小的k个元素，否则返回Sa中所有元素+Sb中小的k-|Sa|个元素。

伪代码：

PARTITION(A, p, r)         //partition过程 p为第一个数，r为最后一个数
1  x ← A[r]               //以最后一个元素作为主元
2  i ← p - 1
3  for j ← p to r - 1
4       do if A[j] ≤ x
5             then i ← i + 1
6                  exchange A[i] <-> A[j]
7  exchange A[i + 1] <-> A[r]
8  return i + 1

RANDOMIZED-PARTITION(A, p, r)      //随机快排的partition过程
1  i ← RANDOM(p, r)                                 //i  随机取p到r中个一个值
2  exchange A[r] <-> A[i]                         //以随机的 i作为主元
3  return PARTITION(A, p, r)            //调用上述原来的partition过程

RANDOMIZED-SELECT(A, p, r, i)       //以线性时间做选择，目的是返回数组A[p..r]中的第i 小的元素
1  if p = r          //p=r，序列中只有一个元素 
2      then return A[p]
3  q ← RANDOMIZED-PARTITION(A, p, r)   //随机选取的元素q作为主元 
4  k ← q - p + 1                     //k表示子数组 A[p…q]内的元素个数，处于划分低区的元素个数加上一个主元元素
5  if i == k                        //检查要查找的i 等于子数组中A[p....q]中的元素个数k
6      then return A[q]        //则直接返回A[q] 
7  else if i < k       
8      then return RANDOMIZED-SELECT(A, p, q - 1, i)   
          //得到的k 大于要查找的i 的大小，则递归到低区间A[p，q-1]中去查找
9  else return RANDOMIZED-SELECT(A, q + 1, r, i - k)
          //得到的k 小于要查找的i 的大小，则递归到高区间A[q+1，r]中去查找。

#include <iostream>
#include <assert.h>

using namespace std;
int *getmink(int a[],int left,int right,int k)
{
 assert(a!=nullptr||k>left||k<right)
 if (k==right+1)
 {
  return a;
 } 
 //选取key值为中位数的中位数
 int midIndex = (left + right)/2; 
 if(a[left] < a[midIndex]) 
    swap(a[left], a[midIndex]); 
 if(a[right] < a[midIndex]) 
    swap(a[right], a[midIndex]); 
 if(a[right] < a[left]) 
    swap(a[right], a[left]); 
 swap(a[left], a[right]);
 int key=a[right];
 int i = left;
 int h=i-1;
 int j = right-1; 
    for (;i<=j;i++)
    {
  if (a[i]
  {
   h++;
   swap(a[h],a[i]);
  }
 }
 swap(a[h+1],a[right]);
 //由于在搜索下半部分时k一般情况下比h+1小所以无法输出结果，这里用k+left与h+1进行比较，由于h+1是

//在left基础上得到的，所以每次递归中对k+left，这样保证了我们在高半部分时是获得k-h-1个数
 if ((h+1) == k+left) 
  return a; 
 else if ((h+1)>k+left) 
  return getmink(a, left, h+1, k); 
 else return getmink(a, h+1, right, k-h-1); 
}
int main()
{
 int a[] = {7, 8, 9, 54, 6, 4, 11, 1, 2,33,0,23,12,5};
 getmink(a,0,sizeof(a)/sizeof(int)-1,5);
 cout<<a[0]<<endl;
 cout<<a[1]<<endl;
 cout<<a[2]<<endl;
 cout<<a[3]<<endl;
 cout<<a[4]<<endl;
 return 0;
}