class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        sort(nums.begin(),nums.end());
        return nums[nums.size()-k];
    }
};

class Solution {
public:
    void swap(int &a , int &b)
    {
        int tmp = b;
        b = a;
        a = tmp;
    }
    int part(vector<int>& nums , int left , int right)
    {
        int key = nums[left];
        while(left<right)
        {
            while(left < right && nums[right] <= key) right--;
            swap(nums[left] , nums[right]);
            while(left < right && nums[left] >= key) left++;
            swap(nums[left] , nums[right]);
        }
        return left;
    }
    void quick_sort(vector<int>& nums , int left , int right)
    {
        if(left > right) return;
        int mid = part(nums,left,right);
        quick_sort(nums,left,mid-1);
        quick_sort(nums,mid+1,right);
    }
    int findKthLargest(vector<int>& nums, int k) {
        quick_sort(nums,0,nums.size()-1);
        return nums[k-1];
    }
};

class Solution {
public:
    void quickSort(vector<int>& arr, int left, int right) 
    {
    // 定义枢轴
    int pivot = arr[(left + right) / 2];
    //int pivot = arr[left]; 也可以
    // 定义两个指针
    int i = left;
    int j = right;
    // 当左指针比右指针小时继续循环
    while (i <= j)
    {
        // 左指针从左往右扫描，直到找到一个元素比枢轴大
        while (arr[i] > pivot) i++;
        // 右指针从右往左扫描，直到找到一个元素比枢轴小
        while (arr[j] < pivot) j--;
        // 如果两个指针没有相遇，交换它们所指向的元素
        if (i <= j)
         {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
    }
    // 如果左边还有元素，递归左边的排序
    if (left < j) quickSort(arr, left, j);
    // 如果右边还有元素，递归右边的排序
    if (i < right) quickSort(arr, i, right);
    }
    int findKthLargest(vector<int>& nums, int k) {
        quickSort(nums,0,nums.size()-1);
        return nums[k-1];
    }
};