快排

class Solution {
public:

    void back (vector<int>& nums, int left, int right, int k) {
        
        if (left >= right) {
            return;
        }

        int i = left, j = right, base = nums[left], tmp = 0;
        while (i < j){
            while( nums[j] >= base && i < j ) {
                j--;
            }
            while( nums[i] <= base && i < j ) {
                i++;
            }
        

            if ( i < j ) {
                tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
            } 
        }

        

        nums[left] = nums[i];
        nums[i] = base;

        // if (i == nums.size() - k ) {
        //     return nums[i];
        // } else if (i > nums.size() - k) {
        //    return back(nums, left, i - 1, k);
        // } else { 
        //    return back(nums, i + 1, right, k);
        // } 

        back(nums, left, i - 1, k);
        back(nums, i + 1, right, k);

    }

    int findKthLargest(vector<int>& nums, int k) {
        for (auto item : nums) {
            cout << item <<" ";
        }

        cout << endl;
        back(nums, 0 , nums.size() - 1, k);

        for (auto item : nums) {
            cout << item << " " ;
        }
        cout <<endl;

        return 0;

    }
};

快排是在最后的时候

二分法

class Solution {
public:

    int back (vector<int>& nums, int left, int right, int k) {
        
        // if (left >= right) {
        //     return;
        // }

        int i = left, j = right, base = nums[left], tmp = 0;
      
        while (i < j){
            while( nums[j] >= base && i < j ) {
                j--;
            }
            while( nums[i] <= base && i < j ) {
                i++;
            }
        

            if ( i < j ) {
                tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
            } 
        }


        nums[left] = nums[i];
        nums[i] = base;

        if (i == nums.size() - k ) {
            return nums[i];
        } else if (i > nums.size() - k) {
           return back(nums, left, i - 1, k);
        } else { 
           return back(nums, i + 1, right, k);
        } 

       

    }

    int findKthLargest(vector<int>& nums, int k) {
        for (auto item : nums) {
            cout << item <<" ";
        }

        cout << endl;
        int m = back(nums, 0 , nums.size() - 1, k);

        for (auto item : nums) {
            cout << item << " " ;
        }
        cout <<endl;

        return m;

    }
};