中位数

给定一个未排序的整数数组，找到其中位数。
中位数是排序后数组的中间值，如果数组的个数是偶数个，则返回排序后数组的第N/2个数。

样例
给出数组[4, 5, 1, 2, 3]， 返回 3
给出数组[7, 9, 4, 5]，返回 5

快速排序的思想，我只需要排一边就可以，可以接近O(n)的复杂度。

public class Solution080 {
    /**
     * @param nums: A list of integers
     * @return: An integer denotes the middle number of the array
     */
    public static void main(String[] args) {
        int[] nums = {4,5,1,2,3,3};
        int result = median(nums);
        System.out.println(result);
    }
    public static int median(int[] nums) {
        if (nums.length == 1){
            return nums[0];
        }
        return sub(nums, 0, nums.length-1, (nums.length-1)/2);
    }
    
    private static int sub(int[] nums, int start, int end, int size) {
        int p = partition(nums, start, end);
        if (p == size) {
            return nums[p];
        }else if (p > size){
            return sub(nums, start, p - 1, size);
        }else{
            return sub(nums, p + 1, end, size);
        }
    }

    private static int partition(int[] nums, int start, int end) {
        int pivot = nums[end];
        int j = start;
        for (int i = start; i < end; i++) {
            if (nums[i] < pivot) {
                exch(nums, i, j);
                j++;
            }
        }
        exch(nums, j, end);
        return j-1;
    }

    private static void exch(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp; 
    }
}