Memahami Algoritma Isih Buih (dengan Contoh dalam Java)

Penjelasan terperinci Isih Buih: algoritma isihan mudah

Isih gelembung ialah salah satu algoritma pengisihan yang paling mudah. Ia berfungsi dengan berulang kali membandingkan elemen bersebelahan dan menukarnya jika ia tidak teratur. Contohnya, jika susunan isihan menaik, elemen bersebelahan dibandingkan dan elemen yang lebih besar diletakkan di sebelah kanan. Dalam setiap lelaran, kami hanya membandingkan elemen yang tidak diisih dan meletakkan elemen terbesar pada kedudukan terakhir elemen yang tidak diisih dalam tatasusunan.

Algoritma ini sesuai dinamakan isihan gelembung kerana elemen bergerak ke arah sebelah kanan tatasusunan pada setiap lelaran, seperti gelembung yang naik ke permukaan air.

Cara isihan gelembung berfungsi

Katakan kita mahu mengisih tatasusunan ini dalam tertib menaik:

Lelaran pertama

Dalam lelaran pertama, kami cuba mengalihkan elemen terbesar ke penghujung tatasusunan. Jadi kami akan berulang kali membandingkan elemen bersebelahan dan menukarnya jika ia tidak teratur.

Elemen yang telah dialihkan ke kedudukan yang betul dianggap diisih.

Mengikuti lelaran

Proses ini diulang untuk semua lelaran sehingga tatasusunan diisih. Dalam setiap lelaran, kami hanya membandingkan elemen yang tidak diisih kerana elemen yang diisih sudah berada dalam susunan yang betul.

Kami mengulangi tatasusunan n-1 kali, dengan n ialah panjang tatasusunan. Iaitu, memandangkan tatasusunan kami mempunyai enam elemen, kami hanya mengulangi tatasusunan sebanyak lima kali. Ini kerana, selepas lelaran kelima, lima elemen telah diletakkan pada kedudukan yang betul, jadi elemen terakhir yang tidak diisih dianggap diisih. Selepas semua lelaran selesai, kita akan mendapat tatasusunan yang diisih.

Pelaksanaan jenis gelembung

public class BubbleSortTest {
    public static void main(String[] args) {
        int[] arr = {8, 2, 6, 4, 9, 1};
        System.out.println("未排序数组: " + Arrays.toString(arr));
        bubbleSort(arr);
        System.out.println("已排序数组: " + Arrays.toString(arr));
    }

    public static void bubbleSort(int[] arr) {
        int size = arr.length;

        // 循环遍历数组 size-1 次
        for (int i = 0; i < size - 1; i++) {
            // 比较相邻元素
            for (int j = 0; j < size - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

Menjalankan kod ini akan mencetak output berikut dalam konsol:

<code>未排序数组: [8, 2, 6, 4, 9, 1]
已排序数组: [1, 2, 4, 6, 8, 9]</code>

Dalam pelaksanaan isihan gelembung ini, kami akan mengulangi tatasusunan setiap kali, walaupun tatasusunan sudah diisih. Kami boleh mengoptimumkan lagi kod supaya pengisihan berhenti setelah tatasusunan telah diisih.

Isih gelembung yang dioptimumkan

public static void bubbleSortOptimised(int[] arr){
    int size = arr.length;
    boolean swapped;

    // 循环遍历数组 size-1 次
    for (int i = 0; i < size - 1; i++) {
        swapped = false;
        // 比较相邻元素
        for (int j = 0; j < size - i - 1; j++) {
            if (arr[j] > arr[j+1]){
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;

                swapped = true;
            }
        }

        // 如果没有交换，则数组已排序
        if(!swapped) break;
    }
}

Dengan pelaksanaan ini, jika kami cuba mengisih tatasusunan yang telah diisih, kami hanya akan mengulang sekali dan berhenti apabila tiada pengisihan berlaku.

Kerumitan jenis gelembung

Kerumitan masa:

Kes terbaik (O(n)):

Senario kes terbaik ialah tatasusunan input sudah diisih. Algoritma hanya mengulang tatasusunan sekali untuk memeriksa sama ada ia diisih dan tidak melakukan sebarang pertukaran.

Purata kes (O(n²)):

Apabila elemen tatasusunan input berada dalam susunan rawak. Algoritma mesti berulang beberapa kali dan melakukan swap untuk mengisih tatasusunan.

Kes terburuk (O(n²)):

Senario kes terburuk ialah tatasusunan input diisih dalam susunan terbalik. Algoritma melalui n-1 lelaran dan melakukan bilangan swap maksimum.

Kerumitan ruang O(1):

Isih gelembung ialah algoritma pengisihan di tempat, iaitu, ia tidak memerlukan sebarang memori tambahan yang berkadar dengan saiz tatasusunan input.

Kesimpulan

Isih gelembung ialah algoritma yang mudah difahami dan dilaksanakan. Walau bagaimanapun, disebabkan kerumitan masa yang tinggi, ia tidak sesuai untuk memproses set data yang besar. Isih gelembung boleh digunakan apabila bekerja dengan set data yang kecil atau apabila anda tidak mengambil berat tentang kerumitan.

Atas ialah kandungan terperinci Memahami Algoritma Isih Buih (dengan Contoh dalam Java). Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!