Пузырьковая сортировка для изменения сортировки с пропуском

Я столкнулся с проблемой и нуждаюсь в вашем руководстве. В основном мне удалось создать этот метод Bubble Sort. Как я могу изменить это на Gap Sort, который вместо того, чтобы каждый раз сравнивать соседние элементы по списку, сравнивает элементы, которые находятся на расстоянии некоторого числа (i) позиций друг от друга, где (i) - целое число меньше, чем n. Например, первый элемент будет сравниваться с (i + 1) элементом, 2-й элемент с (i + 2) элементом, n-й элемент с (n-i) элементом и т. д. Одна итерация завершается, когда все элементы что можно сравнить, сравнивали. На следующей итерации i уменьшается на некоторое число больше 1, и процесс продолжается до тех пор, пока i не станет меньше 1.

public static void bubbleSort (Comparable[] data, int maxlength){
    int position, scan;
    Comparable temp;

    for (position = maxlength; position >= 1; position--){
        for (scan = 0; scan <= position – 1; scan++){
            if (data[scan].compareTo(data[scan+1]) > 0){
                // Swap the values
                temp = data[scan];
                data[scan] = data[scan + 1];
                data[scan + 1] = temp;
            }
        }
    }
}

java sorting bubble-sort gaps-in-data
person serge    schedule 03.04.2012    source источник
comment
Вы ищете реализацию GapSort? посмотрите второй пост по этой ссылке: daniweb.com/software -разработка/java/threads/238791/сортировка по промежутку   -  person Federico Vera    schedule 03.04.2012
comment
Спасибо. а можешь кое-что объяснить? двойной КФ = 1,3; почему это полезно?   -  person serge    schedule 03.04.2012
comment
Идея состоит в том, чтобы начать с большого зазора и уменьшать его на каждом цикле. SF — это что-то вроде коэффициента сжатия (я предполагаю, что в посте имеется в виду что-то вроде коэффициента сжатия), который в данном случае составляет около 76% (это означает, что на каждой итерации разрыв уменьшается до 76% от исходного значения).   -  person Federico Vera    schedule 03.04.2012
comment
Как примечание, если ваши объекты реализуют Comparable, самый простой и быстрый способ их сортировки обычно Arrays.sort()...   -  person Federico Vera    schedule 03.04.2012
comment
круто я понял! благодарю вас   -  person serge    schedule 03.04.2012
comment
Чтобы закрыть вопрос, я добавил комментарий в качестве ответа. знак равно   -  person Federico Vera    schedule 03.04.2012

Ответы (1)


arrow_upward
1
arrow_downward

Этот код (найден на http://www.daniweb.com/software-development/java/threads/238791/gap-sort) может помочь вам:

public static void gapSort (Comparable [] data, int size) {  
    int index;
    int gap, top;
    Comparable temp;
    boolean exchanged;

    double SF = 1.3;
    gap = size;

    do {
        exchanged = false;
        gap = (int) (gap / SF);
        if (gap == 0){
            gap = 1;
        }
        for (index = 1; index <= size - gap; index++) {
            if (data [index].compareTo(data [index + gap]) > 0) {
                temp = data [index];
                data [index] = data [index + gap];
                data [index + gap] = temp;
                exchanged = true;
            }
        }
    } while (exchanged || gap > 1);
}

Помните, что самый простой способ отсортировать массив объектов, реализующих интерфейс Comparable, обычно Arrays.Sort()

person Federico Vera    schedule 03.04.2012