最小的k个数

　　题目来源：《剑指offer》面试题30

　　题目：输入n个整数，找出其中最小的k个数。例如输入4，5，1，6，2，7，3，8这8个数字，则最小的4个数字是1、2、3、4.

　　解法一：利用快速排序Partition的思想来解决这个问题。如果基于数组的第k个数字来调整，使得比第k个数字小的所有数字都位于数组的左边，比第k个数字大的所有数字都位于数组的右边。这样调整之后，位于数组中左边的k个数字就是最小的k个数字（这k个数字不一定是排序的）。

　　采用这种思想是有限制的。我们需要修改输入的数组，因为函数Partition会调整数组中数字的顺序。

　　时间复杂度O(n)

void GetLeastNumbers(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, start, end);

    while (index != k - 1) {
        if (index > k - 1) {
            end = index - 1;
            index = Partition(input, n, output, k);
        } else {
            start = index + 1;
            index = Partition(input, n, output, k);
        }
    }

    for (int i = 0; i < k; i++)
        output[i] = input[i];
}

　　解法二：可以利用k堆排序来解决这个问题。这种方法没有修改数组并且适合海量数据处理。

　　　　　　时间复杂度O(nlgn)

void BuildMaxHeap(int* numbers, int len) {
    for (int i = len / 2; i >= 0; i--) {
        AdjustDown(numbers, i, len - 1);
    }
}

void AdjustDown(int* numbers, int key, int heap_size) {
    int temp = numbers[key];
    for (int child = key << 1 + 1; child <= heap_size; key = child) {
        if (child < heap_size && numbers[child] < numbers[child + 1])
            child++;

        if (temp < numbers[child])
            a[i] = a[child];
        else 
            break;
    }

    numbers[key] = temp
}

void GetLeastNumbers(int* input, int n, int *output, int k) {
    if (input == NULL || output == NULL || k > n || n <= 0 || k <= 0)
        return;

    int index = 0;
    for (; index < k; index++)
        output[index] = input[index];
    BuildMaxHeap(output, k);
    for (;index < n; index++) {
        if (numbers[index] < output[0]) {
            output[0] = numbers[index];
            AdjustDown(numbers, 0, k - 1);
        } 
    }
}