Сортировка методом пузырька

251

25 октября 2017, 03:22

Нужно создать сортировку массива методом пузырька, когда пузырек "тонет" (с конца массива до начала, НЕ сортировка по убыванию) В чем проблема? Вот мой код:

public static void main(String[] args) {
    int[] b = {1333, 44, 565, 783, 673, 22, 46, 8};
    for (int i = b.length-1; i >= 0; i--) {
        for (int j = i - 1; j > 0; j--) {
            if (b[j] > b[j + 1]) {
                swap(b, j, j + 1);
            } else {
                break;
            }
        }
    }
         for (int n : b) {
        System.out.print(n + " ");
    }
}
static void swap(int[] a, int left, int right) {
    if (left != right) {
        int temp = a[left];
        a[left] = a[right];
        a[right] = temp;
    }
}

Результат вывода на экран:

1333 8 22 44 565 783 673 46

Почему не правильно проходит сортировка? Подскажите, пожалуйста!

Answer 1

Давайте для начала напишем обычный канонический пузырёк.

for (int i = 0; i < b.length; i++)
        for (int j = 0; j < b.length-1; j++)
            if (b[j] > b[j +1])
                swap(b, j, j +1);

Если уже решили оптимизировать, то

for (int i = 0; i < b.length; i++)
        for (int j = 0; j < b.length-i-1; j++)
            if (b[j] > b[j +1])
                swap(b, j, j +1);

Уже тут видно, что else break ломает всё...

Дальше мы хотим делать это с конца. Окей. Первый цикл вообще (!) ни на что не влияет, хоть с конца идти, хоть сначала, поэтому так и оставим. Второй надо развернуть. Если развернуть в лоб - будет совсем некрасиво. Меняем порядок обхода в j+1 на j-1 Получается в целом нормально

for (int i = 0; i < b.length; i++)
        for (int j = b.length-1; j > i; j--)
            if (b[j] < b[j - 1])
                swap(b, j, j - 1);

P.S. проверку из swap уберите, оно не нужна.

ПОСЛЕДНИЕ ВОПРОСЫ

Все вопросы

ТОП-10

Все популярные вопросы

Сортировка методом пузырька

Модификация Jira с помощью api/rest api

Вопрос по C# OpenQA.Selenium

Почему не работают массивы в LINQ to entities

Видимость контрола на форме C#