Bubble Sort to модификация сортировки по гэпу - PullRequest
Новая
       12

Bubble Sort to модификация сортировки по гэпу

0 голосов
/ 03 апреля 2012

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

1 Ответ

1 голос
/ 03 апреля 2012

Этот код (найденный на 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()

...