c语言求最小的k个数

解题思路

先看一下要求：时间复杂度O(nlogn)，直接找一个O(nlogn)的排序算法，然后返回k个元素即可。这里我使用希尔排序。 讲一下希尔排序：记住三层循环：最外层是分组长度，假设11个元素，那么分组有 5，2，1三个，第二层循环是从第二块开始，也就是每一个分组的第二个元素进行该组内的插入排序，所以第三层循环是当前分组元素位置前的元素个数。依次交换即可。时间复杂度为O(nlogn)，满足要求

 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param input int整型一维数组 
 * @param inputLen int input数组长度
 * @param k int整型 
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
//浅写一个交换算法吧
void swap(int *a,int *b){
    int temp=*a;
    *a=*b;
    *b=temp;
}
//写一个希尔排序吧
void shell_sort(int array[],int len){
    for(int gap=len>>1;gap>0;gap=gap>>1){
        for(int i=gap;i<len;i++){
            for(int j=i-gap;j>=0;j-=gap){
                if(array[j+gap]<array[j])
                    swap(&array[j+gap],&array[j]);
            }
        }
    }
}
int* GetLeastNumbers_Solution(int* input, int inputLen, int k, int* returnSize ) {
    // write code here
    shell_sort(input, inputLen);
    *returnSize=k;
    return input;
}