题目：

输入n个整数，找出其中最小的k个数。

例子说明：

例如输入4 、5 、1、6、2、7、3 、8 这8 个数字，则最小的4 个数字是1 、2、3 、4

解题思路：

解法一：O(n)时间算法，只有可以修改输入数组时可用。

可以基于Partition函数来解决这个问题。如果基于数组的第k个数字来调整，使得比第k个数字小的所有数字都位于数组的左边，比第k个数字大的所有数字都位于数组的右边。这样调整之后，位于数组中左边的k个数字就是最小的k 个数字（这k 个数字不一定是排序的〉。

解法二： O（nlogk）的算法，精剧适合处理海量数据。

先创建一个大小为k的数据容器来存储最小的k个数字，接下来我们每次从输入的n个整数中读入一个数．如果容器中已有的数字少于k个，则直接把这次读入的整数放入容器之中：如果容器中己有k 数字了，也就是容器己满，此时我们不能再插入新的数字而只能替换已有的数字。找出这己有的k 个数中的最大值，然后1在这次待插入的整数和最大值进行比较。如果待插入的值比当前己有的最大值小，则用这个数替换当前已有的最大值：如果待插入的值比当前已有的最大值还要大，那么这个数不可能是最小的k个整数之一，于是我们可以抛弃这个整数。

因此当容器满了之后，我们要做3 件事情： 一是在k个整数中找到最大数： 二是有可能在这个容器中删除最大数： 三是有可能要插入一个新的数字。我们可以使用一个大顶堆在O(logk）时间内实现这三步操作。

代码实现

Partition方法:

/**
 排序 数组

 @param inputArray 输入数组(原数组)
 @param startIndex 起始 索引
 @param endIndex 终止 索引
 @param k 前 k 个 元素
 */
void qiuckSort(int *inputArray, int startIndex, int endIndex, int k) {
    if(inputArray == NULL || startIndex < 0 || k < 0) {
        return;
    }
    
    int leftIndex = startIndex;
    int rightIndex = endIndex;
    int compareValue = inputArray[leftIndex];
    
    while (leftIndex < rightIndex) {
        // 从后 往前 遍历 找到 比compareValue 小的 数
        while (leftIndex < rightIndex && inputArray[rightIndex] > compareValue) {
            rightIndex -- ;
        }
        inputArray[leftIndex] = inputArray[rightIndex];
        // 从前向后 遍历 找到 比compareValue 大的数
        while (leftIndex < rightIndex && inputArray[leftIndex] < compareValue) {
            leftIndex ++;
        }
        inputArray[rightIndex] = inputArray[leftIndex];
    }
    inputArray[leftIndex] = compareValue;
    
    // 前半部分 太长
    if (leftIndex > k - 1) {
        qiuckSort(inputArray, startIndex, leftIndex - 1, k);
    }
    // 前半部分 太短
    else if(leftIndex < k - 1) {
        qiuckSort(inputArray, leftIndex + 1, endIndex, k);
    }
}

/**
 获取 最小 的 前K 个 数

 @param inputArray 输入数组(原数组)
 @param inputLength 原数组 长度
 @param k 最小的前K 个数
 */
void getLeastNumbersOne(int *inputArray, int inputLength, int k) {
    if(inputArray == NULL || inputLength == 0) {
        return ;
    }
    
    if (k == 0) {
        return;
    }
    qiuckSort(inputArray, 0, inputLength - 1, k);
}

大顶堆方法:

#import <Foundation/Foundation.h>


/**
 交互 数组 中 的两个 数字

 @param numArray 待排序 数组
 @param a 数组 下标
 @param b 数组 下标
 */

void heapSwap(int *numArray,int a ,int b){
    int temp= numArray[a];
    numArray[a] = numArray[b];
    numArray[b] = temp;
}

/**
 调整 堆

 @param numArray 待排序 数组
 @param nodeOrder 结点 序号
 @param arrayLength 数组 长度
 */
void heapAdjust(int *numArray, int nodeOrder, int arrayLength) {
    // 先 保存 当前 值
    int tmpValue = numArray[nodeOrder];
    //从nodeOrder结点的左子结点开始，也就是2i+1处开始 遍历调整 各个非叶子节点
    for(int tmpIndex = nodeOrder * 2 + 1; tmpIndex < arrayLength; tmpIndex = tmpIndex * 2 + 1){
        if (tmpIndex + 1 < arrayLength && numArray[tmpIndex] < numArray[tmpIndex + 1]) {
            tmpIndex ++;
        }
        
        //如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
        if (numArray[tmpIndex] > tmpValue) {
            numArray[nodeOrder] = numArray[tmpIndex];
            nodeOrder = tmpIndex;
        }
        else {
            break;
        }
    }
    numArray[nodeOrder] = tmpValue;
}

/**
 构建 堆

 @param numArray 待排序 数组
 @param arrayLength 数组 长度
 */
void buildHeap(int *numArray, int arrayLength) {
    if(numArray == NULL) {
        return;
    }
    
    if (arrayLength == 0) {
        return;
    }
    
    // 非叶子节点最大序号值为arrayLength/2
    for (int tmpIndex = arrayLength/2 - 1; tmpIndex >= 0; tmpIndex--) {
        heapAdjust(numArray, tmpIndex, arrayLength);
    }
}


/**
 堆排序

 @param numArray 待排序 数组
 @param arrayLength 数组 长度
 */
void heapSort (int *numArray, int arrayLength) {
    if(numArray == NULL) {
        return;
    }
    
    if (arrayLength == 0 ||
        arrayLength == 1) {
        return;
    }
    
    // 构建 大顶堆
    buildHeap(numArray, arrayLength);
    
    // 倒序 交互 最大数
    for(int tmpIndex = arrayLength - 1; tmpIndex > 0; tmpIndex--) {

        heapSwap(numArray, 0, tmpIndex);
        
        heapAdjust(numArray, 0, tmpIndex);
    }
    
}

/**
 
 获取 最小 的 前K 个 数
 @param inputArray 输入数组(原数组)
 @param inputLength 原数组 长度
 @param outputArray 输出 数组
 @param outputLenghth 输出 数组 长度
 */
void getLeastNumberTwo(int *inputArray, int inputLength, int *outputArray, int outputLenghth) {
    if(inputArray == NULL || inputLength == 0) {
        return ;
    }
    
    if (outputArray == NULL || outputLenghth == 0) {
        return;
    }
    
    // 遍历 字符串
    for (int tmpIndex = 0; tmpIndex < inputLength; tmpIndex++) {
        // 小于 输出 数组 长度
        if (tmpIndex < outputLenghth) {
            outputArray[tmpIndex] = inputArray[tmpIndex];
            // 当 输出 数组 满时
            if (tmpIndex == (outputLenghth - 1)) {
                // 构建 堆
                buildHeap(outputArray, outputLenghth);
            }
        }
        // 大于 输出 数组 长度
        else {
            // 小于 数组 最大值
            if(inputArray[tmpIndex] < outputArray[0]) {
                outputArray[0] = inputArray[tmpIndex];
                heapAdjust(outputArray, 0, outputLenghth);
            }
        }
    }
}


int main(int argc, const char * argv[]) {
    @autoreleasepool {
        int a[7] = {0, 16, 20, 3, 11, 17, 8};
        int b[6] = {0};
        getLeastNumberTwo(a, 7, b, 6);
        for(int tmpIndex = 0 ;tmpIndex < 6; tmpIndex++) {
            printf("%d ", b[tmpIndex]);
        }
    }
    return 0;
}