题解 | #最小的K个数#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param input int整型一维数组 
 * @param inputLen int input数组长度
 * @param k int整型 
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数

 */



#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
static int B[10010];
void Merge(int A[], int low, int mid, int high)
{
    int i,j,k;
    for (k=low; k<=high; k++) B[k] = A[k];

    for (i=low, j=mid+1, k=i; i<=mid&&j<=high; k++)
    {
        if (B[i]<=B[j]) A[k] =B[i++];
        else A[k] = B[j++];
    }
    while (i<=mid) A[k++] = B[i++];
    while (j<=high) A[k++] = B[j++]; 
}

void MergeSort(int A[], int low, int high)
{
    if (low<high)
    {
        int mid = (low + high) /2;
        MergeSort(A,  low, mid);
        MergeSort(A, mid+1, high);
        Merge(A, low, mid, high);
    }
}
int* GetLeastNumbers_Solution(int* input, int inputLen, int k, int* returnSize ) {
    // write code here
    // 快速排序
    // QuickSort(input, 0,  inputLen-1);
    * returnSize = k;
    MergeSort(input, 0, inputLen-1);

    for (int i =0; i<inputLen;i++) printf("%d ", input[i]);
    return input;

}