算法-求无序数组的中位数（快速排序）

中位数，就是数组排序后处于数组最中间的那个元素。如果数组长度是奇数，最中间就是位置为(n+1)/2的那个元素；如果数组长度是偶数，中位数就是位置n/2和位置为n/2+1的两个元素的和除以2的结果。

    /**
     * 基于快速排序查找中位数
     * 定义一个key，一般取数组最右边的元素为key，然后再定义两个变量start和end
     * start为首元素索引，end为尾元素索引
     * 然后从后往前找，找到第一个比key小的元素，没找到则end--，找到则将当前start位置的元素值置为当前end位置的元素值
     * 然后再start++
     * 接着再从前往后找，找到第一个比key大的元素，没找到则start++，找到则将当前end位置的元素值置为当前start位置的元素值
     * 最后当start==end的时候，将当前start位置的元素值置为key
     * 接着递归调用，按当前start==end的位置，分成两半
     * 左边到start-1，右边从start+1开始
     *
     * @param array
     * @param left
     * @param right
     */
    private static void quickSortSearchMedian(int[] array, int left, int right) {
        if (left < 0) {
            return;
        }
        if (right >= array.length) {
            return;
        }
        if (left >= right) {
            return ;
        }
        int key = array[left];
        int start = left;
        int end = right;
        while (start < end) {
            // 从右边往左边找，找到第一个小于key的值，则索引--
            while (start < end && array[end] >= key) {
                end--;
            }
            if (start < end) {
                array[start] = array[end];
                start++;
            }
            // 从左边往右边找，找到第一个大于key的值，则索引++
            while (start < end && array[start] <= key) {
                start++;
            }
            if (start < end) {
                array[end] = array[start];
                end--;
            }
        }
        // start == end
        array[start] = key;
        quickSortSearchMedian(array, left, start - 1);
        quickSortSearchMedian(array, start + 1, right);
    }

    /**
     * 求中位数
     * 如果数组长度为奇数，则是第(n+1)/2个，即下标为(n+1)/2-1
     * 如果数组长度为偶数，则是第n/2和n/2+1个之和除以2，即下标为n/2-1和n/2的两个数的和除以2
     * @param array
     */
    public static void searchMedian(int[] array) {
        quickSortSearchMedian(array, 0, array.length - 1);
        if ((array.length % 2) == 0) {
            int i = array[array.length/2-1];
            int j = array[array.length/2];
            System.out.println((i+j)/2.0);
        } else {
            System.out.println(array[(array.length + 1) / 2 - 1]);
        }
    }