题解 | #最小的K个数#C NC119

//看了堆排序的代码，理解后自己写的处女-小根堆，堆排序
void swap(int*a,int*b){             //交换函数，参数是地址
    int temp;
    temp=*a;
    *a=*b;
    *b=temp;
 }
 void lowdui(int *arr,int k,int n){        //执行一次父节点k,和双子的比较，本题选的小根堆，值小的放到父结点上
    int x=2*k;
    if(x+1>=n){
        return;
    }

    if((x+1)<n&&arr[x+1]<arr[k]){         //左边比较，父节点值大，就交换
        swap(&arr[x+1],&arr[k]);

    }
    x++;                                 //右孩子
    if((x+1)<n&&arr[x+1]<arr[k]){          //右边比较，父节点大的就交换
        swap(&arr[x+1],&arr[k]);
    }
 }
 void lowsort(int*arr,int n){           //全部检查，不符合交换，lowsort 一次就是找出了最小值放在arr[0]处
    for(int i=n/2-1;i>=0;i--){            //从最后一个父节点开始，往前
        lowdui(arr,i,n);
    }
 }

int* GetLeastNumbers_Solution(int* input, int inputLen, int k, int* returnSize ) {
    // write code here
    int* returnarr=(int*)malloc(sizeof(int)*k);     //申请数组，存放返回数组
    int n=inputLen;
    int j=0;
    for(int i=n-1;i>n-k-1;i--){                     //只需要k个，就n-k-1，i是最后一个数下标
        lowsort(input,i+1);                         //注意参数，i+1长度的调整一次，最小的放在了input[0]处
        swap(&input[0],&input[i]);                  //最小值交换一下，随后长度减一
        returnarr[j++]=input[i];                    //这里直接把最小的那个放进返回数组
    }
    *returnSize=k;//这个是数组长度，题干给的注释是数组行数，真服了（就按数组长度）。就自己运行几次就知道这个是啥了
    return returnarr;
}