使用快排求第K大数值

// note: 使用异或交互数值，需判断两数不相等
public class FindKthNum {

    public static void main(String[] args) {

        int[] arrs = new int[]{3, 2, 3, 1, 2, 4, 5, 5, 6};

        int t = new FindKthNum().findKthLargest(arrs, 4);
        System.out.print(t);
    }

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

    private int QuickSort(int[] arr, int first, int last, int target) {

        if (first > last) {
            return -1;
        }
        int p = paritition(arr, first, last);
        if (p == target) {
            return arr[p];
        }

        // 快排剪枝用于查找第K大的数,只需在其中一半进行查找
        int t = -1;
        if (target > p) {
            t = QuickSort(arr, p + 1, last, target);
        } else if (target < p) {
            t = QuickSort(arr, first, p - 1, target);
        }

        return t;
    }

    private int paritition(int[] arr, int first, int last) {
        // 随机化快排，优化？
        int idx = (int) (Math.random() * (last - first) + first);
        if (idx != first) {
            arr[idx] = arr[idx] ^ arr[first];
            arr[first] = arr[idx] ^ arr[first];
            arr[idx] = arr[idx] ^ arr[first];
        }
        int p = arr[first];
        int left = first + 1;
        int right = last;

        for (int i = left; i <= right; i++) {
            if (arr[i] >= p) {
                while (left <= right) {
                    if (arr[right] < p) {
                        arr[left] = arr[left] ^ arr[right];
                        arr[right] = arr[left] ^ arr[right];
                        arr[left] = arr[left] ^ arr[right];
                        left++;
                        right--;
                        break;
                    }
                    right--;
                }
            } else {
                left++;
            }
        }

        left--;
        if (p != arr[left]) {
            arr[first] = arr[left] ^ arr[first];
            arr[left] = arr[left] ^ arr[first];
            arr[first] = arr[left] ^ arr[first];
        }
        return left;
    }
}