求最小K個數的快速排序解法

1. 題目分析

因為隻需要求解最小k個部分，是以不一定需要對左右兩半都進行遞歸。在代碼上來說，隻有遞歸部分和快排不同，分組部分不需要更改。

2. 左右部分的遞歸控制

左右部分遞歸控制方法如下：

（1）[l,...,r] ==> [l,..,p], [p+1,.., r] 
（2）關注最小k個部分落在哪裡：
     i. 隻落在左半時，p > k, 隻在左半進行遞歸   
     ii. 至少有部分在右半時，p <= k, 隻在右半進行遞歸
           

3. 代碼

class Solution {
public:
    int partation(int l, int r, vector<int>& arr) {
        int pos = l;
        for (int i=l; i<r; i++) {
            if (arr[i] < arr[r]) {
                swap(arr[i], arr[pos]);
                pos++;
            }
        }
        swap(arr[pos], arr[r]);
        return pos;
    }
    // [l,...,r] ==> [l,..,p], [p+1,.., r]
    // 關注最小k個部分落在哪裡：
    // 隻落在左半時，p > k, 隻在左半進行遞歸
    // 至少有部分在右半時，p <= k, 隻在右半進行遞歸 
    void qsort(int l, int r, int k, vector<int>& arr) {
        if (l<r) {
            int p = partation(l, r, arr);
            if (p > k) qsort(l, p-1, k, arr);
            if (p <= k) qsort(p+1, r, k, arr);
        }
    }
    vector<int> smallestK(vector<int>& arr, int k) {
        qsort(0, arr.size()-1, k, arr);
        return vector<int>(arr.begin(), arr.begin()+k);
    }
};
           

4. 結果