题解 | #最小的K个数##手写快排#

/**

• 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
• @param input int整型一维数组
• @param inputLen int input数组长度
• @param k int整型
• @return int整型一维数组
• @return int* returnSize 返回数组行数
• C语言声明定义全局变量请加上static，防止重复定义 */

int cmpfunc(void const *a, void const *b)
{
    return *(int*)a - *(int*)b;
}

//快排
void QuickSort(int *azArray, int Lift, int Right)
{
    int i = Lift;
    int j = Right;
    int iPivot = 0;
    if (i < j)
    {
        iPivot = azArray[i];	//选择基准元素
        while (i != j)
        {
            while (i < j && azArray[j] > iPivot)		//从右边开始找到第一个小于基准元素
                j--;
            if (i < j )
            {
                azArray[i] = azArray[j];	//L与 R找到的小于iPivot的元素交换位置
                i++;
            }
            while (i < j && azArray[i] < iPivot)	//变换顺序，从左边开始找到第一个大于基准元素
                i++;
            if (i < j)
            {
                azArray[j] = azArray[i];	//R与 L找到的大于iPivot的元素交换位置
                j--;
            }
        }//循环，直到L=R;此时L坐标左边的元素均小于pivot，右边的元素均大于pivot。
        azArray[i] = iPivot;	//pivot赋值给此时的L坐标元素
        QuickSort(azArray, Lift, i - 1);		//分别开始递归
        QuickSort(azArray, i + 1, Right);
    }
        
    return ;
}

int* GetLeastNumbers_Solution(int* input, int inputLen, int k, int* returnSize ) {
    // write code here
    int *iReArray = NULL;
    int i = 0;
    if (NULL == input || 0 == k)
        return NULL;
    if (k > inputLen)
        return input;
    
    iReArray = (int*)malloc(sizeof(int) * k);
    memset(iReArray, 0, (sizeof(int) * k));
    //qsort(input, inputLen, sizeof(int), cmpfunc);
    QuickSort(input, 0, inputLen - 1);
    for(i = 0; i < k; i++)
    {
        iReArray[i] = input[i];
    }
    *returnSize = k;
    return iReArray;
}