剑指offer编程题—最小的K个数

题目描述
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

思路整理
很简单的一题。基本思想就是排序，正好复习一下常用的排序算法。

1. 快速排序
   1）基本思想：快速排序是对冒泡排序的一种改进。其基本思想就是通过一趟排序将待排序序列分割为独立的两部分，其中一部分记录的关键字都比另一部分记录的关键字小，再分别对这两部分使用快排，直到整个序列有序为止。
   2）时间复杂度：O(nlogn).
   3）快速排序在所有时间复杂度为O(nlogn)的排序算法中，性能是最好的；
   4）但是快排需要一个栈的辅助空间；
   5）在初始待排序序列有序或基本有序的情况下，快排退化为冒泡排序，此时不适合用快排。

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        if(input.size()<k || k<=0) return vector<int>();
        quickSort(input,k);
        vector<int> res(input.begin(),input.begin()+k);
        return res;
    }
    void quickSort(vector<int> &input,int k){
        Qsort(input,0,input.size()-1,k);
    }
    void Qsort(vector<int> &input,int low,int high,int k){
        if(low<high){
            int vipot=Partition(input,low,high);
            if(vipot>=k-1) Qsort(input,low,vipot-1,k);  //如果左边记录已经达到k个，则只用对左边元素进行排序，不用管右边较大的记录
            else{
                Qsort(input,low,vipot-1,k);
                Qsort(input,vipot+1,high,k);
            }
        }
    }
    int Partition(vector<int> &input,int low,int high){
        int tmp=input[low];
        while(low<high){
            while(low<high && tmp<=input[high]) --high;
            input[low]=input[high];
            while(low<high && tmp>=input[low]) ++low;
            input[high]=input[low];
        }
        input[low]=tmp;
        return tmp;
    }
};

2. 堆排序
   1）基本思想：通过将无序序列转换为堆，可以直接获得最小值或最大值，取出堆顶元素（最小值或最大值），令剩余的记录重新构建成堆，可以获得次小值或次大值，如此反复，可以获得一个有序序列。
   2）时间复杂度：相比快速排序，堆排序在最坏的情况其时间复杂度也是O(nlogn);
   3）堆排序只需要一个辅助记录空间；
   4）堆排序的时间主要耗费在建初堆和反复调整堆的筛选上；
   5）对于记录数比较少的序列，不适合用堆排序。

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        if(input.size()<k || k<=0) return vector<int>();
        vector<int> res;
        HeapSort(input,res,k);
        return res;
    }
    void HeapSort(vector<int> &input,vector<int> &res,int k) {
        int i;
        for(i=input.size()/2;i>=0;--i){
            HeapAdjust(input,i,input.size()-1);
        }
        int tmp;
        for(i=input.size()-1;i>=0;--i){
            res.push_back(input[0]); //每次将堆顶的最小记录放入结果集
            if(res.size()==k) break; //获取到最小的k个记录后退出排序算法，避免超时
            tmp=input[i];
            input[i]=input[0];
            input[0]=tmp;
            HeapAdjust(input,0,i-1);
        }
    }
    void HeapAdjust(vector<int> &input,int s,int m){ //筛选堆使其为最小堆
        int tmp=input[s];
        int i;
        for(i=2*s+1;i<=m;i=2*i+1){
            if(i+1<=m && input[i+1]<input[i]) ++i;
            if(input[i]>=tmp) break;
            input[s]=input[i];
            s=i;
        }
        input[s]=tmp;
    }
};

3. 归并排序
   1）基本思想：归并排序的基本思想就是将待排序序列分割为两个独立的部分，再依次对分的的两部分进行归并排序，之后再将二者合并；
   2）时间复杂度：无论再最好情况下还是在最坏情况下，归并排序的时间复杂度都是O(nlogn);
   3）归并排序是一种稳定的排序算法；
   4）空间复杂度：O(n).显然归并排序不是就地排序。

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        if(input.size()<k || k<=0) return vector<int>();
        MergeSort(input,0,input.size()-1,k);
        vector<int> res(input.begin(),input.begin()+k);
        return res;
    }
    void MergeSort(vector<int> &input,int low,int high,int k){
        if(low<high){
            int mid=(low+high)/2;
            MergeSort(input,low,mid,k);
            MergeSort(input,mid+1,high,k);
            Merge(input,low,mid,high);
        }
    }
    void Merge(vector<int> &input,int low,int mid,int high){
        vector<int> res;
        int i=low;
        int j=mid+1;
        while(i<=mid && j<=high){
            if(input[i]<=input[j]){
                res.push_back(input[i]);
                ++i;
            }
            else{
                res.push_back(input[j]);
                ++j;
            }
        }
        while(i<=mid){
            res.push_back(input[i]);
            ++i;
        }
        while(j<=high){
            res.push_back(input[j]);
            ++j;
        }
        for(i=0;i<res.size();++i){
            input[low+i]=res[i];
        }
    }
};

4. 优先级队列
   优先级队列内部也是使用的堆排序技术，默认是构建大根堆，也就是优先级队列能始终保证队头元素最大，但是其内部不一定是完全有序的。

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        if(input.size()<k || k<=0) return vector<int>();
        priority_queue<int,vector<int>,less<int> > q;
        int i=0;
        while(i<input.size()){
            q.push(input[i]);
            if(q.size()>k) q.pop();
            ++i;
        }
        vector<int> res;
        while(!q.empty()){
            res.push_back(q.top());
            q.pop();
        }
        return res;
    }
};