Пример сортировки пузырьков Java

Пузырьковая сортировка – это самый простой алгоритм сортировки, он сравнивает первые два элемента, если первый больше второго, меняет их местами, продолжает выполнять (сравнивает и меняет местами) для следующей пары соседних элементов. Затем он снова начинается с первых двух элементов, сравнивает, меняет местами, пока больше не потребуется никаких замен.

1. Объяснение

#unsorted data -> [99, 88, 55, 77, 1, 66]

#1 iteration.
#1.1 -> [99, 88, 55, 77, 1, 66] -> [88, 99, 55, 77, 1, 66]
#1.2 -> [88, 99, 55, 77, 1, 66] -> [88, 55, 99, 77, 1, 66]
#1.3 -> [88, 55, 99, 77, 1, 66] -> [88, 55, 77, 99, 1, 66]
#1.4 -> [88, 55, 77, 99, 1, 66] -> [88, 55, 77, 1, 99, 66]
#1.5 -> [88, 55, 77, 1, 99, 66] -> [88, 55, 77, 1, 66, 99]

#2 iteration.
#2.1 -> [88, 55, 77, 1, 66, 99] -> [55, 88, 77, 1, 66, 99]
#2.2 -> [55, 88, 77, 1, 66, 99] -> [55, 77, 88, 1, 66, 99]
#2.3 -> [55, 77, 88, 1, 66, 99] -> [55, 77, 1, 88, 66, 99]
#2.4 -> [55, 77, 1, 88, 66, 99] -> [55, 77, 1, 66, 88, 99]

#3 iteration.
#3.1 -> [55, 77, 1, 66, 88, 99] -> [55, 77, 1, 66, 88, 99] {no swap}
#3.2 -> [55, 77, 1, 66, 88, 99] -> [55, 1, 77, 66, 88, 99]
#3.3 -> [55, 1, 77, 66, 88, 99] -> [55, 1, 66, 77, 88, 99]

#4 iteration.
#4.1 -> [55, 1, 66, 77, 88, 99] -> [1, 55, 66, 77, 88, 99]
#4.2 -> [1, 55, 66, 77, 88, 99] -> [1, 55, 66, 77, 88, 99] {no swap}

#5 iteration.
#5.1 -> [1, 55, 66, 77, 88, 99] -> is_sorted = true, break;

Вот реализация сортировки пузырьков Java.

    public static void sort(int[] input) {

        int inputLength = input.length;
        int temp;
        boolean is_sorted;

        for (int i = 0; i < inputLength; i++) {

            is_sorted = true;

            for (int j = 1; j < (inputLength - i); j++) {

                if (input[j - 1] > input[j]) {
                    temp = input[j - 1];
                    input[j - 1] = input[j];
                    input[j] = temp;
                    is_sorted = false;
                }

            }

            // is sorted? then break it, avoid useless loop.
            if (is_sorted) break;

            System.out.println("\n");
            
        }
        
    }

2. Пример сортировки пузырьков Java

Полный пример, демонстрирующий использование алгоритма пузырьковой сортировки для сортировки простого набора данных, поддерживает порядок возрастания или убывания.

package com.mkyong;

import java.util.Arrays;
import java.util.stream.Collectors;

public class BubbleSortExample{

    public static void main(String[] args) {

        int[] array = {99, 88, 55, 77, 1, 66};

        System.out.print("unsorted data: ");
        printArray(array);

        System.out.print("ascending order: "); //1,55,66,77,88,99
        bubble_sort(array);

        printArray(array);

        System.out.print("descending order: "); //99,88,77,66,55,1
        bubble_sort(array, false);

        printArray(array);

    }

    private static void bubble_sort(int[] input) {
        bubble_sort(input, true);
    }

    private static void bubble_sort(int[] input, boolean ascending) {

        int inputLength = input.length;
        int temp;
        boolean is_sorted;

        for (int i = 0; i < inputLength; i++) {

            is_sorted = true;

            for (int j = 1; j < (inputLength - i); j++) {

                if (ascending) {
                    if (input[j - 1] > input[j]) {
                        temp = input[j - 1];
                        input[j - 1] = input[j];
                        input[j] = temp;
                        is_sorted = false;
                    }
                } else {
                    if (input[j - 1] < input[j]) {
                        temp = input[j - 1];
                        input[j - 1] = input[j];
                        input[j] = temp;
                        is_sorted = false;
                    }

                }

            }

            // is sorted? then break it, avoid useless loop.
            if (is_sorted) break;

        }

    }

    private static void printArray(int[] data) {
        String result = Arrays.stream(data)
                .mapToObj(String::valueOf)
                .collect(Collectors.joining(","));
        System.out.println(result);
    }

}

Выход

unsorted data: 99,88,55,77,1,66
ascending order: 1,55,66,77,88,99
descending order: 99,88,77,66,55,1

1. Объяснение

2. Пример сортировки пузырьков Java

Рекомендации

Читайте ещё по теме: