剑指offer JZ-29

题目描述：输入一个数组， 和K， 返回前K个最小的值。
分析： 对数组排序 + 提取前K 个值
边界（K超过数组长度， 返回空数组）
这里先给出我的代码思路：

1. sort(input)

2. get_res(input,k)

   int len =input.szie();
   if(len>1){
    sort(input);
   }
   vector<int> res;
   if(k<=len){
    for(int i=0; i<k; i++)
        res.puish_back(input[i])
   } 
   return  res;

   这里没有给出具体的排序代码， 主要是因为，排序算法是一个常考点。一般考察八种：
   名称-----|-----平均复杂度---|----最好--|----最坏----|-----空间------|--稳定---|
   冒泡排序 | | | | |稳定
   给出冒泡排序的代码：

   vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
   
        int len =input.size();
        if (len>=1){
            //---------bullbe sort------ time O(N^2)   space O(1)
            int tmp=0;
            for(int i=0; i<len; i++)
                for(int j=0; j<len-i-1; j++)
                    if(input[j]>input[j+1]){
                        tmp = input[j];
                        input[j] = input[j+1];
                        input[j+1] = tmp;
                    }
        }
        //---------out res
        vector<int> res;
        if(k<=len){
            for(int i=0; i<k; i++)
                res.push_back(input[i]);
        }
        return res;
    }

   快速排序| | || | 不稳定（位置会变动）
   以下给出快速排序的代码（利用了分治思想）

   class Solution {
   public:
    vector<int> sort_quick(vector<int> arr, int left, int right){
        if (left > right) return arr; 
        //左右哨兵 
        int l=left, r=right;
        //base number 
        int base = arr[left]; 
        while(l != r){
            //远离base number 的先走 
            while( arr[r]>=base && r>l) r--;
            while( arr[l]<=base && r>l) l++;
            if (l!=r){
                int tmp = arr[r]; arr[r] = arr[l]; arr[l] = tmp; 
            }
        } 
        //l=r,
        arr[left] = arr[l];  arr[l] = base;
        arr = sort_quick(arr, left, l-1);
        arr = sort_quick(arr, r+1, right);
   
        return arr;
    }
   
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
   
        int len =input.size();
        if (len>=1){
            //---------bullbe sort------ time O(N^2)   space O(1)
            int tmp=0;
            input = sort_quick(input, 0, input.size()-1);
        }
        //---------out res
        vector<int> res;
        if(k<=len){
            for(int i=0; i<k; i++)
                res.push_back(input[i]);
        }
        return res;
    }
   };

   堆排序也是一种常考的排序方法
   堆排序| | | ||不稳定
   堆排序是利用维护种特殊的满二叉树结构， 大顶堆(父大于子)， 小顶堆（父小于子）来每次提取最大值， 并更新维护剩下的树结构。
   这里给出大顶堆代码：

   class Solution {
   public:
    vector<int> adjust(vector<int> arr, int root, int len){
        int lchild = root*2+1;
        int rchild = root*2+2;
        int maxind = root;
        //record max ind
        if(lchild< len && arr[lchild] > arr[maxind]) maxind = lchild;
        if(rchild< len && arr[rchild] > arr[maxind]) maxind = rchild; 
   
        if(maxind != root){
            int tmp = arr[root];
            arr[root] = arr[maxind];
            arr[maxind] = tmp;
            arr= adjust(arr, maxind, len); 
        } 
        return arr;
    } 
    vector<int> sort_heap(vector<int> arr){
        int len = arr.size();
        for(int i=len/2-1; i>=0; i--)
            arr = adjust(arr, i, len);
        for(int i=len-1; i>0; i--){
            int t=arr[0];
            arr[0]=arr[i];     arr[i]=t;
            arr = adjust(arr, 0, i);
        } 
   
        return arr;
    }
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
   
        int len =input.size();
        if (len>=1){
            //---------bullbe sort------ time O(N^2)   space O(1)
            int tmp=0;
            input = sort_heap(input);
        }
        //---------out res
        vector<int> res;
        if(k<=len){
            for(int i=0; i<k; i++)
                res.push_back(input[i]);
        }
        return res;
    }
   };

   题目是前K个最小， 如果使用小顶堆， 只需要排出前K个即可， 这里给出代码：

   class Solution {
   public:
    vector<int> adjust_min(vector<int> arr, int root, int len){
        int lchild = root*2+1;
        int rchild = root*2+2;
        int minind = root;
        //record max ind
        if(lchild< len && arr[lchild] < arr[minind]) minind = lchild;
        if(rchild< len && arr[rchild] < arr[minind]) minind = rchild; 
   
        if(minind != root){
            int tmp = arr[root];
            arr[root] = arr[minind];
            arr[minind] = tmp;
   
            arr= adjust_min(arr, minind, len); 
        } 
        return arr;
    }
   
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        int len =input.size();
        vector<int> res;
        if (k<=len){
            for(int i=len/2-1; i>=0; i--)
                input = adjust_min(input, i, len);
   
            for(int i=len-1; i>len-1-k; i--){
                res.push_back(input[0]);
                input[0]=input[i]; 
                input = adjust_min(input, 0, i);
            }
        }
        //---------out res
        return res;
    }
   };

   其他排序方法，后续跟新并