输入n个整数，找出其中最小的k个数

    解法1：需要修改输入的数组，基于partition快速排序来做，时间复杂福O（N）

    分析：基于数组的第k个元素来调整，使的比第k个数大的所有数字放到数组的右边，这样，数组左边k个就是最小的k个数字

void GetLestNumber(int *input, int n, int *output, int k){	if (input == NULL || output == NULL || k > n || n <= 0 || k <= 0)		return;	int start = 0;	int end = n - 1;	int index = Partition(input, n, start, end);	while (index != k - 1)	{		if (index > k - 1)		{			end = index - 1;			index = Partition(input, n, start, end);		}		else		{			start = index + 1;			index = Partition(input, n, start, end);		}	}	for (int i = 0; i < k; ++i)	{		output[i] = input[i];	}}

解法二：

    分析：先创建一个大小为k的数据容器来存储最小的k个数字，接着每次从输入的n个整数中读入一个数，如果容器中少于k个数则直接放，若大于则表示容器以满，此时找出容器中最大值，然后拿输入的值和最大值比较，若待插入的数小于最大值，则直接替换。

    最大堆的结构每次可以在O（1）得到最大值，但需要o（logk）时间来完成删除及插入

    红黑树同上，但是代码简于大堆

void GetLestNumber(int *input, int n, int *output, int k){        if (input == NULL || output == NULL || k > n || n <= 0 || k <= 0)          return; int start = 0;      int end = n - 1;    int index = Partition(input, n, start, end);        while (index != k - 1)      {           if (index > k - 1)               {                   end = index - 1;                    index = Partition(input, n, start, end);            }           else                {                   start = index + 1;                  index = Partition(input, n, start, end);            }   }   for (int i = 0; i < k; ++i)      {           output[i] = input[i];       }}解法二：    分析：先创建一个大小为k的数据容器来存储最小的k个数字，接着每次从输入的n个整数中读入一个数，如果容器中少于k个数则直接放，若大于则表示容器以满，此时找出容器中最大值，然后拿输入的值和最大值比较，若待插入的数小于最大值，则直接替换。    最大堆的结构每次可以在O（1）得到最大值，但需要o（logk）时间来完成删除及插入const int N = 1000;const int k = 10;void AdjustDown(int *a, int size, int parent){ int child = (parent - 1) / 2;       while (child < size)     {           if (child+1
     
      a[child + 1])                      child++;            if (a[child]>a[parent])          {                   swap(a[child], a[parent]);                  parent = child;                     child = (parent - 1) / 2;           }           else                        break;      }}void GetTopK(int*a){  assert(k < N);   int top[k]; for (int i = 0; i < k; i++)      {           top[i] = a[i];      }   for (int i = (k - 2) / 2; i >= 0; i++)   {           AdjustDown(top, k, i);      }   for (int i = N-k-1; i < N; i++)  {           if (a[i]>top[0])         {                   top[0] = a[i];                      AdjustDown(top, k, 0);              }   }}