Jika anda pernah mendengar kaedah pengisihan dalam pengaturcaraan, kemungkinan besar ia adalah algoritma isihan gelembung. Ia adalah satu yang terkenal. Setiap pengaturcara mengetahui jenis gelembung (atau sekurang-kurangnya mendengarnya semasa belajar) bukan kerana ia adalah algoritma pengisihan terbaik di dunia, tetapi yang paling mudah. Algoritma ini biasanya digunakan untuk tujuan pembelajaran atau anda mungkin mendapatkannya sebagai tugas dalam Java Junior Interview anda. Algoritma isihan Bubble Java sangat mudah difahami, namun ia bukanlah algoritma yang cekap. Bagaimanapun, mari kita fikirkan.
Langkah 1: kita akan melalui tatasusunan. Algoritma bermula dengan dua elemen pertama (dengan indeks 0 dan 1), 8 dan 7, dan menyemak sama ada ia berada dalam susunan yang betul. Jelas sekali, 8 > 7, jadi kami menukarnya. Seterusnya, kita melihat elemen kedua dan ketiga (indeks 1 dan 2), kini ini adalah 8 dan 1. Atas sebab yang sama, kita menukarnya. Untuk kali ketiga kami membandingkan 8 dan 2 dan, sekurang-kurangnya 8 dan 5. Kami membuat empat pertukaran secara keseluruhan: (8, 7), (8, 1), (8, 2) dan (8, 5). Nilai 8, yang terbesar dalam tatasusunan ini, muncul di penghujung senarai ke kedudukan yang betul.
Hasil daripada langkah pertama algoritma isihan Bubble adalah tatasusunan seterusnya:
Langkah 2. Melakukan perkara yang sama dengan (7,1), (7,2) dan (7,5). 7 kini berada di kedudukan kedua terakhir, dan kita tidak perlu membandingkannya dengan "ekor" senarai, ia sudah disusun.
Hasil daripada langkah kedua algoritma isihan Bubble adalah tatasusunan seterusnya:
Seperti yang anda lihat, tatasusunan ini sudah diisih. Bagaimanapun, algoritma Bubble Sort harus berjalan sekurang-kurangnya sekali lagi. Langkah3. Kami akan melalui tatasusunan sekali lagi. Tiada apa-apa untuk ditukar di sini, jadi jika kami menggunakan algoritma Isih Buih "diperbaiki" (dengan menyemak sama ada sekurang-kurangnya satu pertukaran pada langkah sebelumnya telah dibuat) langkah ini adalah yang terakhir.
Apa yang menyusun
Pertama sekali, anda perlu memahami apa itu pengisihan secara umum dan apa yang boleh kita isi dalam program Java. Jika kita boleh membandingkan dua atau lebih elemen atau objek dengan mana-mana atributnya, ini bermakna ia boleh diisih mengikut atribut ini. Contohnya, nombor dalam susunan menaik atau menurun atau perkataan mengikut abjad. Oleh itu, unsur-unsur mestilah setanding antara satu sama lain. By the way, unsur-unsur apa? Di Jawa, kita boleh membandingkan elemen Koleksi. Contohnya kita boleh mengisih Array atau ArrayList integer, Strings dan sebagainya.Bagaimana jenis gelembung berfungsi
Katakan, kita perlu mengisih tatasusunan integer dalam tertib menaik, iaitu, daripada nombor terkecil kepada nombor terbesar. Mula-mula, kita akan mengikuti keseluruhan tatasusunan dan membandingkan setiap 2 elemen jiran. Jika mereka berada dalam susunan yang salah (jiran kiri lebih besar daripada yang kanan), kami menukar mereka. Pada hantaran pertama pada penghujung ia akan muncul elemen terbesar (jika kita mengisih dalam tertib menaik). Anda boleh berkata, elemen terbesar "muncul". Itulah sebab nama algoritma isihan Bubble. Kami mengulangi langkah pertama dari elemen pertama hingga seterusnya hingga terakhir. Kami mempunyai elemen kedua terbesar di tempat seterusnya hingga terakhir. Dan sebagainya. Kita boleh meningkatkan sedikit algoritma dengan menyemak sama ada sekurang-kurangnya satu pertukaran pada langkah sebelumnya telah dibuat. Jika tidak, kita berhenti berjalan di sepanjang array.Contoh jenis gelembung
Mari kita susun tatasusunan integer, satu, anda boleh lihat di bawah pada gambar.




Bubble sort kod Java
Realisasi Java jenis buih
Mari kita cipta dua kaedah untuk isihan Bubble. Yang pertama, bubbleSort(int[] myArray) ialah satah. Ia berjalan melalui tatasusunan setiap kali. Yang kedua, optimizedBubbleSort(int myArray[]) dioptimumkan dengan menghentikan algoritma jika gelung dalaman tidak menyebabkan sebarang pertukaran. Kaunter menunjukkan kepada anda berapa banyak langkah yang anda lakukan semasa mengisih. Di sini kami mendapat realisasi Java jenis Bubble:
import java.util.Arrays;
public class BubbleSortExample {
// Plane Bubble sort example
public static int[] bubbleSort(int[] myArray) {
int temp = 0; // temporary element for swapping
int counter = 0; // element to count quantity of steps
for (int i = 0; i < myArray.length; i++) {
counter = i + 1;
for (int j = 1; j < (myArray.length - i); j++) {
if (myArray[j - 1] > myArray[j]) {
// swap array’s elements using temporary element
temp = myArray[j - 1];
myArray[j - 1] = myArray[j];
myArray[j] = temp;
}
}
}
System.out.println("Steps quantity, non optimized = " + counter);
return myArray;
}
// An optimized version of Java Bubble Sorting
static int[] optimizedBubbleSort(int myArray[]) {
int temp;
boolean swapped;
int counter = 0; // element to count quantity of steps
for (int i = 0; i < myArray.length - 1; i++) {
counter = i + 1;
swapped = false;
for (int j = 0; j < myArray.length - i - 1; j++) {
// counter++;
if (myArray[j] > myArray[j + 1]) {
// swap arr[j] and arr[j+1]
temp = myArray[j];
myArray[j] = myArray[j + 1];
myArray[j + 1] = temp;
swapped = true;
}
} // counter = i;
// If there weren't elements to swap in inner loop, then break
if (swapped == false) {
break;
}
}
System.out.println("steps quantity, optimized = " + counter);
return myArray;
}
public static void main(String[] args) {
int arr[] = {8, 7, 1, 2, 5};
int arr1[] = {8, 7, 1, 2, 5};
System.out.println("Array arr Before Bubble Sort");
// we use java.util.Arrays toString method to print the array
System.out.println(Arrays.toString(arr));
System.out.println("Array arr After Bubble Sort");
System.out.println(Arrays.toString(bubbleSort(arr)));
System.out.println("Array arr1 Before Bubble Sort");
System.out.println(Arrays.toString(arr1));
System.out.println("Array arr1 After Optimized Bubble Sort");
System.out.println(Arrays.toString(optimizedBubbleSort(arr1)));
}
}
Hasil kerja algoritma Java sort Bubble:
Array arr Before Bubble Sort
[8, 7, 1, 2, 5]
Array arr After Bubble Sort
Steps quantity, non optimized = 5
[1, 2, 5, 7, 8]
Array arr1 Before Bubble Sort
[8, 7, 1, 2, 5]
Array arr1 After Optimized Bubble Sort
steps quantity, optimized = 3
[1, 2, 5, 7, 8]
GO TO FULL VERSION