求最小的k個(gè)數(shù)

輸入n個(gè)整數(shù)，找出其中最小的k個(gè)數(shù)

    解法1：需要修改輸入的數(shù)組，基于partition快速排序來(lái)做，時(shí)間復(fù)雜福O（N）

    分析：基于數(shù)組的第k個(gè)元素來(lái)調(diào)整，使的比第k個(gè)數(shù)大的所有數(shù)字放到數(shù)組的右邊，這樣，數(shù)組左邊k個(gè)就是最小的k個(gè)數(shù)字

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];
	}
}

解法二：

    分析：先創(chuàng)建一個(gè)大小為k的數(shù)據(jù)容器來(lái)存儲(chǔ)最小的k個(gè)數(shù)字，接著每次從輸入的n個(gè)整數(shù)中讀入一個(gè)數(shù)，如果容器中少于k個(gè)數(shù)則直接放，若大于則表示容器以滿，此時(shí)找出容器中最大值，然后拿輸入的值和最大值比較，若待插入的數(shù)小于最大值，則直接替換。

    最大堆的結(jié)構(gòu)每次可以在O（1）得到最大值，但需要o（logk）時(shí)間來(lái)完成刪除及插入

    紅黑樹同上，但是代碼簡(jiǎn)于大堆

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];
       }
}
解法二：
    分析：先創(chuàng)建一個(gè)大小為k的數(shù)據(jù)容器來(lái)存儲(chǔ)最小的k個(gè)數(shù)字，接著每次從輸入的n個(gè)整數(shù)中讀入一個(gè)數(shù)，如果容器中少于k個(gè)數(shù)則直接放，若大于則表示容器以滿，此時(shí)找出容器中最大值，然后拿輸入的值和最大值比較，若待插入的數(shù)小于最大值，則直接替換。
    最大堆的結(jié)構(gòu)每次可以在O（1）得到最大值，但需要o（logk）時(shí)間來(lái)完成刪除及插入
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<size&&a[child]>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);
              }
   }
}