Isih Buih

Isih gelembung mengisih tatasusunan dalam berbilang fasa. Setiap pas secara berturut-turut menukar elemen jiran jika elemen tidak teratur. Algoritma isihan gelembung membuat beberapa laluan melalui tatasusunan. Pada setiap hantaran, pasangan jiran berturut-turut dibandingkan. Jika pasangan berada dalam susunan menurun, nilainya ditukar; jika tidak, nilai kekal tidak berubah. Teknik ini dipanggil isih gelembung atau isihan tenggelam, kerana nilai yang lebih kecil secara beransur-ansur "bergelembung" menuju ke atas dan nilai yang lebih besar tenggelam ke bawah. Selepas hantaran pertama, elemen terakhir menjadi yang terbesar dalam tatasusunan. Selepas hantaran kedua, elemen kedua hingga terakhir menjadi yang kedua terbesar dalam tatasusunan. Proses ini diteruskan sehingga semua elemen diisih.

Rajah di bawah (a) menunjukkan hantaran pertama isihan gelembung pada tatasusunan enam elemen (2 9 5 4 8 1). Bandingkan elemen dalam pasangan pertama (2 dan 9), dan tiada pertukaran diperlukan kerana ia sudah teratur. Bandingkan unsur dalam pasangan kedua (9 dan 5), dan tukar 9 dengan 5 kerana 9 lebih besar daripada 5. Bandingkan unsur dalam pasangan ketiga (9 dan 4), dan tukar 9 dengan 4. Bandingkan unsur dalam yang keempat pasangan (9 dan 8), dan tukar 9 dengan 8. Bandingkan elemen dalam pasangan kelima (9 dan 1), dan tukar 9 dengan 1. Pasangan yang dibandingkan diserlahkan dan nombor yang telah diisih dicondongkan dalam Rajah di bawah.

Hasil pertama meletakkan nombor terbesar (9) sebagai yang terakhir dalam tatasusunan. Dalam laluan kedua, seperti yang ditunjukkan dalam Rajah di bawah (b), anda membandingkan dan memesan pasangan elemen secara berurutan. Tidak perlu mempertimbangkan pasangan terakhir, kerana elemen terakhir dalam tatasusunan sudah menjadi yang terbesar. Dalam laluan ketiga, seperti yang ditunjukkan dalam Rajah di bawah (c), anda membandingkan dan memesan pasangan elemen secara berurutan kecuali dua elemen terakhir, kerana ia sudah teratur. Jadi dalam pas kth, anda tidak perlu mempertimbangkan elemen k - 1 yang terakhir, kerana ia sudah dipesan.

Algoritma untuk isihan gelembung diterangkan dalam kod di bawah.

untuk (int k = 1; k < list.length; k++) {
// Lakukan pas kth
untuk (int i = 0; i < list.length - k; i++) {
jika (senarai[i] > senarai[i + 1])
tukar senarai[i] dengan senarai[i + 1];
}
}

Perhatikan bahawa jika tiada pertukaran berlaku dalam pas, tidak perlu melakukan hantaran seterusnya, kerana semua elemen sudah diisih. Anda boleh menggunakan sifat ini untuk menambah baik algoritma dalam kod di atas seperti dalam kod di bawah.

boolean needNextPass = benar;
untuk (int k = 1; k < list.length && needNextPass; k++) {
// Tatasusunan mungkin diisih dan pas seterusnya tidak diperlukan
needNextPass = palsu;
// Lakukan pas kth
untuk (int i = 0; i < list.length – k; i++) {
jika (senarai[i] > senarai[i + 1]) {
tukar senarai[i] dengan senarai[i + 1];
needNextPass = benar; // Pas seterusnya masih diperlukan
}
}
}

Algoritma boleh dilaksanakan dalam kod di bawah

Dalam kes terbaik, algoritma isihan gelembung hanya memerlukan hantaran pertama untuk mendapati tatasusunan sudah diisih—tiada pas seterusnya diperlukan. Memandangkan bilangan perbandingan ialah n - 1 dalam pas pertama, masa kes terbaik untuk isihan gelembung ialah O(n).

Dalam kes yang paling teruk, algoritma isihan gelembung memerlukan n - 1 pas. Pas pertama membuat perbandingan n - 1; pas kedua membuat n - 2 perbandingan; dan seterusnya; hantaran terakhir membuat 1 perbandingan. Oleh itu, jumlah bilangan perbandingan ialah:

Oleh itu, masa terburuk untuk jenis gelembung ialah O(n^2).

Atas ialah kandungan terperinci Isih Buih. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!