Prinsip: Bandingkan dua elemen yang berdekatan dan elemen pertukaran dengan nilai besar di ujung kanan.
Ide: Bandingkan dua angka yang berdekatan secara berurutan, tempatkan desimal di depan dan angka besar di belakang. Artinya, pada perjalanan pertama: pertama bandingkan angka pertama dan kedua, letakkan desimal sebelumnya dan angka besar setelahnya. Kemudian bandingkan angka kedua dan angka ketiga, letakkan desimal sebelum dan sesudah angka besar, lanjutkan seperti ini sampai dua angka terakhir dibandingkan, letakkan desimal sebelum dan sesudah angka besar. Ulangi langkah pertama sampai semua penyortiran selesai.
Misalnya: Untuk mengurutkan array: int [] arr = {6,3,8,2,9,1};
Pesanan Pertama:
Jenis Pertama: 6 dan 3 Bandingkan, 6 lebih besar dari 3, posisi swap: 368291
Jenis Kedua: 6 dan 8 Bandingkan, 6 kurang dari 8, tidak ada posisi pertukaran: 368291
Urutan ketiga: 8 dan 2 perbandingan, 8 lebih besar dari 2, posisi swap: 362891
Urutan Keempat: 8 dan 9 Bandingkan, 8 kurang dari 9, tidak ada posisi pertukaran: 362891
Urutan Kelima: 9 dan 1 Bandingkan: 9 lebih besar dari 1, Posisi Pertukaran: 362819
Perjalanan pertama dibandingkan total 5 kali, hasil penyortiran: 362819
---------------------------------------------------------------------
Urutan kedua:
Penyortiran pertama: 3 dan 6 Bandingkan, 3 kurang dari 6, tidak ada posisi pertukaran: 362819
Jenis Kedua: 6 dan 2 Bandingkan, 6 lebih besar dari 2, posisi swap: 326819
Urutan ketiga: 6 dan 8 perbandingan, 6 lebih besar dari 8, tidak ada posisi pertukaran: 326819
Urutan Keempat: 8 dan 1 Bandingkan, 8 lebih besar dari 1, posisi swap: 326189
Perjalanan kedua dibandingkan secara total, dan hasil penyortiran adalah: 326189
---------------------------------------------------------------------
Urutan ketiga:
Sortir Pertama: 3 dan 2 Bandingkan, 3 lebih besar dari 2, posisi swap: 236189
Jenis Kedua: 3 dan 6 Bandingkan, 3 kurang dari 6, tidak ada posisi pertukaran: 236189
Urutan ketiga: 6 dan 1 perbandingan, 6 lebih besar dari 1, posisi swap: 231689
Perjalanan kedua dibandingkan secara total, dan hasil penyortiran adalah: 231689
---------------------------------------------------------------------
Pesanan keempat:
Penyortiran pertama: 2 dan 3 Bandingkan, 2 kurang dari 3, tidak ada posisi pertukaran: 231689
Jenis Kedua: 3 dan 1 Bandingkan, 3 lebih besar dari 1, posisi swap: 213689
Perjalanan kedua dibandingkan secara total, dan hasil penyortiran adalah: 213689
---------------------------------------------------------------------
Urutan kelima:
Sortir Pertama: 2 dan 1 Bandingkan, 2 lebih besar dari 1, posisi swap: 123689
Perjalanan kedua dibandingkan secara total, dan hasil penyortiran adalah: 123689
---------------------------------------------------------------------
Hasil Akhir: 123689
---------------------------------------------------------------------
Dari sini kita dapat melihat bahwa angka N perlu diurutkan, dan N-1 kali diurutkan secara total. Jumlah waktu penyortiran untuk setiap i-pass adalah (NI), sehingga Anda dapat menggunakan pernyataan loop ganda untuk mengontrol berapa kali lapisan luar akan mengontrol berapa kali untuk setiap perjalanan, yaitu,
untuk (int i = 1; i <arr.length-1; i ++) {for (int j = 1; j <arr.length-1-i; j ++) {// Posisi swap}Keuntungan penyortiran gelembung: Setiap kali Anda mengurutkan, Anda akan membandingkan lebih sedikit, karena setiap kali Anda mengurutkan, Anda akan menemukan nilai yang lebih besar. Seperti disebutkan di atas: Setelah perbandingan pertama, angka terakhir harus menjadi angka terbesar. Saat menyortir kedua kalinya, Anda hanya perlu membandingkan angka lain selain dari angka terakhir, dan Anda juga dapat menemukan bahwa angka terbesar berada di peringkat setelah angka yang berpartisipasi dalam perbandingan kedua. Saat membandingkan ketiga kalinya, Anda hanya perlu membandingkan angka lain selain dari dua angka terakhir, dan seterusnya ... dengan kata lain, jika Anda tidak melakukan perbandingan, setiap kali Anda membandingkan sekali, yang mengurangi jumlah algoritma sampai batas tertentu.
Dalam hal kompleksitas waktu:
1. Jika data kami sudah beres, kami hanya perlu melakukan perjalanan untuk menyelesaikan penyortiran. Jumlah perbandingan dan gerakan catatan yang diperlukan keduanya nilai minimum, yaitu: cmin = n-1; mmin = 0; Oleh karena itu, kompleksitas waktu terbaik untuk penyortiran gelembung adalah O (n).
2. Jika sayangnya data kami diperlukan pesanan terbalik, diperlukan pemesanan N-1. Setiap pesanan harus dibandingkan (1≤i≤n-1), dan setiap perbandingan harus dipindahkan ke catatan tiga kali untuk mencapai posisi catatan pertukaran. Dalam hal ini, waktu perbandingan dan gerakan keduanya mencapai maksimum: kompleksitas waktu terburuk dari jenis gelembung adalah: o (n2).
Singkatnya: Total kompleksitas waktu rata -rata dari jenis gelembung adalah: o (n2).
Implementasi Kode:
/ * * Bubble Sort */Public Class Bubblesort {public static void main (string [] args) {int [] arr = {6,3,8,2,9,1}; System.out.println ("Array sebelum menyortir adalah:"); untuk (int num: arr) {system.out.print (num+""); } for(int i=1;i<arr.length;i++){//The outer loop controls the number of sorting times for(int j=1;j<arr.length-i;j++){//The inner loop controls how many times each time it is sorted if(arr[j-1]>arr[j]){ int temp=arr[j]; arr [j] = arr [j-1]; arr [j-1] = temp; }}} System.out.println (); System.out.println ("Array yang diurutkan adalah:"); untuk (int num: arr) {system.out.print (num+""); }}}