kth smallest Element in unsorted array

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.

For example, Given [3,2,1,5,6,4] and k = 2, return 5. Note: You may assume k is always valid, 1 ≤ k ≤ array's length.


Note: this is equivalent to find kth smallest element in unsorted array, just use a.length-k to convert it to kth largest element.





Brute force method:

sort the array and return the asked element.

Better method: quick select
derived from quick sort,but no need to sort the entire array, returns when kth element is figured out.

Basic functions for quick sort/select:

    /**
     * quicksort partition:
     * 1.range is the part of array to deal with(divid and conquer)
     * 2.this method use first element in range as a pivot
     * 3. returned value is index of pivot and pivot is in right position and won't change anymore
     * @param a
     * @param left
     * @param right
     * @return
     */
    private int partition(int[] a, int left, int right) {
        int i = left;
        int j = right + 1;
        while(true) {//a[left] ispivot, someone might use right one, and someone randomly pick on
            while(i < right && a[++i] < a[left]);//move i, until it's a position that's no longer less than pivot
            while(j > left && a[left] < a[--j]);//move j, until it's a position that is no longer greater than pivot
            if(i >= j) {//this is important:only swap when i
                break;
            }//
            swap(a, i, j);//now a[i]>=pivot and a[j] <=pivot, swap them to put them into right range
        }
        swap(a, left, j);//finally put left/pivot to right position
        return j;
    }

    /**
     * basic array two elements swap
     * @param a
     * @param i
     * @param j
     */
    private void swap(int[] a, int i, int j) {
        final int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

Find kth smallest:

   /**
     * QuickSelect
     * Use partition algorithm in Quick Sort
     */
    public int findKthSmallest(int[] nums, int k) {
        //k = nums.length - k;
        int l = 0;
        int r = nums.length - 1;
        while (l < r) {
            final int j = partition(nums, l, r);//j's value is figured out
            if(j < k) {
                l = j + 1;//j and its left are guaranteed to be less or equal to nums[j] 
            } else if (j > k) {
                r = j - 1;
            } else {
                break;
            }
        }
        return nums[k];
    }

Find kth largest element

   /**
     * QuickSelect
     * Use partition algorithm in Quick Sort
     */
    public int findKthLargest(int[] nums, int k) {
        k = nums.length - k;
        findKtheSmallest(nums, nums.length-k);
        return nums[k];
    }