Непонятный алгоритм медианы медиан для поиска k-го элемента

Question

Ниже приведен мой код для попытки понять алгоритм медианы медиан (используя блоки размером 5). Я понимаю, как получить медианы ввода, но я не уверен, как закодировать блок, чтобы повторять ввод до тех пор, пока у меня не будет медианы. Затем, получив эту медиану, я не уверен, как использовать ее как опорную точку для отбрасывания бесполезной информации для разделения ввода. getMediansArray возвращает массив размера ceil(input.length/5) и getMedians просто возвращает медиану из массива (используется только для массивов длины <= 5).

public static int[] findKthElement(int[] input, int k) {
    int numOfMedians = (int) Math.ceil(input.length/5.0);
    int[] medians = new int[numOfMedians];
    medians = getMediansArray(input, medians)

    // (1) This only gets the first iteration of medians of the
    // input. How do I recurse on this until I just have one median?

    // (2) how should I partition about the pivot once I get it?
}

public static int[] getMediansArray(int[] input, int[] medians) {
    int numOfMedians = (int) Math.ceil(input.length/5.0);
    int[] five = new int[5];

    for (int i = 0; i < numOfMedians; i++) {
        if (i != numOfMedians - 1) {
            for (int j = 0; j < 5; j++) {
                five[j] = input[(i*5)+j];
            }
            medians[i] = getMedian(five);
        } else {
            int numOfRemainders = input.length % 5;
            int[] remainder = new int[numOfRemainders];
            for (int j = 0; j < numOfRemainders; j++) {
                remainder[j] = input[(i*5)+j];
            }
            medians[i] = getMedian(five);
        }
    }
    return medians;
}

public static int getMedian(int[] input) {
    Arrays.sort(input);
    if (input.length % 2 == 0) {
        return (input[input.length/2] + input[input.length/2 - 1]) / 2;
    }
    return input[input.length/2];
}

Answer 1

Медиана медиан - это просто улучшенный алгоритм быстрого выбора ( http://en.wikipedia.org/wiki/Quickselect). Несмотря на то, что быстрый выбор имеет среднюю сложность O(n), он может замедлиться до O(n^2) для сложного ввода.

То, что вы делаете после нахождения медианы медиан, - это не что иное, как итерация алгоритма быстрого выбора. Медиана медиан обладает хорошим свойством, что оно всегда будет больше 30% элементов и меньше 30% элементов. Это гарантирует, что быстрый выбор, использующий медиану медиан для оси, будет работать с наихудшей временной сложностью O(n). См. http://en.wikipedia.org/wiki/Median_of_medians

Я предлагаю вам начать с реализации быстрого выбора. Как только вы это сделаете, вы можете использовать код, который вам уже нужен, чтобы выбрать опору на каждом шаге быстрого выбора.

Answer 2

Если я правильно помню ( освежает мою память) Медиана медиан выбирает приблизительную медиану. Я не понимаю, как его можно использовать для выбора k-го элемента.