Kth Largest Element in an Array

This is No.215 in Leetcode.

The description:
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

My own solution is:

class Solution {
    public int findKthLargest(int[] nums, int k) {

        // sort array first
        Arrays.sort(nums);

        // get the length of array
        int length = nums.length;
        int ret = 0;

        for(int i = 0; i < k ; i++){
            ret = nums[length - 1];
            length--;
        }

        return ret;
    }
}

The logical is straight, but I want to talk about another approach: quick sort.

Quick Sort

Quicksort is a divide-and-conquer algorithm. It works by selecting a ‘pivot’ element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively. This can be done in-place, requiring small additional amounts of memory to perform the sorting.

The pseudocode:

 function quicksort(q)
 {
     var list less, pivotList, greater
     if length(q) ≤ 1 
         return q
     else 
     {
         select a pivot value pivot from q
         for each x in q except the pivot element
         {
             if x < pivot then add x to less
             if x ≥ pivot then add x to greater
         }
         add pivot to pivotList
         return concatenate(quicksort(less), pivotList, quicksort(greater))
     }
 }
 ```

 ##### IN-PLACE VERSION
 ``` 
 function partition(a, left, right, pivotIndex)
 {
     pivotValue = a[pivotIndex]
     swap(a[pivotIndex], a[right]) // move pivot to the end
     storeIndex = left
     for i from left to right-1
     {
         if a[i] <= pivotValue
          {
             swap(a[storeIndex], a[i])
             storeIndex = storeIndex + 1
          }
     }
     swap(a[right], a[storeIndex]) // move pivot to current position
     return storeIndex
 }
 ```
 ```
  procedure quicksort(a, left, right)
     if right > left
         select a pivot value a[pivotIndex]
         pivotNewIndex := partition(a, left, right, pivotIndex)
         quicksort(a, left, pivotNewIndex-1)
         quicksort(a, pivotNewIndex+1, right)

For this problem, we can use code below:

 public class Solution {
    public int findKthLargest(int[] nums, int k) {
        return quickSelect(nums, k - 1, 0, nums.length - 1);
    }

    private int quickSelect(int[] arr, int k, int left, int right){
        int pivot = arr[(left + right) / 2];
        int orgL = left, orgR = right;
        while(left <= right){

            while(arr[left] > pivot){
                left ++;
            }

            while(arr[right] < pivot){
                right --;
            }
            // 将两个数互换
            if(left <= right){
                swap(arr, left, right);
                left ++;
                right --;
            }
        }

        if(orgL < right && k <= right) return quickSelect(arr, k, orgL, right);

        if(left < orgR && k >= left) return quickSelect(arr, k, left, orgR);
        return arr[k];

    }

    private void swap(int[] arr, int idx1, int idx2){
        int tmp = arr[idx1] + arr[idx2];
        arr[idx1] = tmp - arr[idx1];
        arr[idx2] = tmp - arr[idx2];

    }
}

So we could use quick sort to sort array first and then get the kth largest element.