Nếu bạn đã từng nghe nói về các phương pháp sắp xếp trong lập trình, rất có thể đó là thuật toán sắp xếp bong bóng. Nó là một trong những nổi tiếng. Mọi lập trình viên đều biết sắp xếp bong bóng (hoặc ít nhất là nghe nói về nó khi học) không phải vì nó là thuật toán sắp xếp tốt nhất trên thế giới, mà là thuật toán dễ nhất. Thuật toán này thường được sử dụng cho mục đích học tập hoặc bạn có thể lấy nó làm nhiệm vụ trong Cuộc phỏng vấn Java Junior của mình. Thuật toán sắp xếp bong bóng của Java rất dễ hiểu, tuy nhiên nó không phải là một thuật toán hiệu quả. Dù sao, chúng ta hãy tìm ra nó.
Bước 1: chúng ta đang đi qua mảng. Thuật toán bắt đầu với hai phần tử đầu tiên (có chỉ số 0 và 1), 8 và 7, và kiểm tra xem chúng có đúng thứ tự không. Rõ ràng, 8 > 7, vì vậy chúng tôi trao đổi chúng. Tiếp theo, chúng tôi xem xét các yếu tố thứ hai và thứ ba (chỉ số 1 và 2), bây giờ đây là 8 và 1. Vì những lý do tương tự, chúng tôi hoán đổi chúng. Lần thứ ba, chúng tôi so sánh 8 và 2 và, ít nhất là 8 và 5. Tổng cộng chúng tôi đã thực hiện bốn lần đổi chỗ: (8, 7), (8, 1), (8, 2) và (8, 5). Giá trị 8, giá trị lớn nhất trong mảng này, xuất hiện ở cuối danh sách ở đúng vị trí.
Kết quả của bước đầu tiên của thuật toán sắp xếp bong bóng hoạt động là mảng tiếp theo:
Bước 2. Làm tương tự với (7,1), (7,2) và (7,5). 7 giờ đã ở vị trí áp chót, và chúng ta không cần so sánh với "đuôi" của danh sách, nó đã được sắp xếp sẵn.
Kết quả của bước thứ hai của thuật toán Sắp xếp bong bóng hoạt động là mảng tiếp theo:
Như bạn có thể thấy, mảng này đã được sắp xếp. Dù sao thì thuật toán Sắp xếp bong bóng sẽ hoạt động ít nhất một lần nữa. Bước 3. Chúng ta sẽ xem qua mảng một lần nữa. Không có gì để trao đổi ở đây, vì vậy nếu chúng ta đang sử dụng thuật toán Sắp xếp bong bóng “cải tiến” (với việc kiểm tra xem có ít nhất một lần trao đổi ở bước trước đó được thực hiện hay không) thì bước này là bước cuối cùng.
sắp xếp là gì
Trước hết, bạn cần hiểu sắp xếp nói chung là gì và chúng ta có thể sắp xếp những gì trong chương trình Java. Nếu chúng ta có thể so sánh hai hoặc nhiều phần tử hoặc đối tượng theo bất kỳ thuộc tính nào của chúng, điều đó có nghĩa là chúng có thể được sắp xếp theo thuộc tính này. Ví dụ: các số theo thứ tự tăng dần hoặc giảm dần hoặc các từ theo bảng chữ cái. Do đó, các yếu tố phải được so sánh với nhau. Nhân tiện, các yếu tố của cái gì? Trong Java, chúng ta có thể so sánh các phần tử của Collections. Ví dụ: chúng ta có thể sắp xếp Array hoặc ArrayList của số nguyên, Chuỗi, v.v.Sắp xếp bong bóng hoạt động như thế nào
Giả sử, chúng ta cần sắp xếp một mảng các số nguyên theo thứ tự tăng dần, tức là từ số nhỏ nhất đến số lớn nhất. Đầu tiên, chúng ta sẽ đi dọc theo toàn bộ mảng và so sánh từng 2 phần tử lân cận. Nếu chúng sai thứ tự (hàng xóm bên trái lớn hơn hàng xóm bên phải), chúng tôi đổi chỗ cho chúng. Ở lần vượt qua đầu tiên ở cuối sẽ xuất hiện phần tử lớn nhất (nếu ta sắp xếp theo thứ tự tăng dần). Bạn có thể nói, yếu tố lớn nhất “bật lên”. Đó là lý do của tên thuật toán sắp xếp bong bóng. Chúng tôi lặp lại bước đầu tiên từ phần tử đầu tiên đến phần tử tiếp theo. Chúng tôi đã có yếu tố lớn thứ hai ở vị trí tiếp theo đến cuối cùng. Và như thế. Chúng ta có thể cải thiện thuật toán một chút bằng cách kiểm tra xem có ít nhất một trao đổi ở bước trước được thực hiện hay không. Nếu không, chúng tôi dừng chạy dọc theo mảng.Ví dụ sắp xếp bong bóng
Hãy sắp xếp mảng các số nguyên, một, bạn có thể thấy hình bên dưới.




Mã Java sắp xếp bong bóng
Thực hiện Java sắp xếp bong bóng
Hãy tạo hai phương thức để sắp xếp bong bóng. Cái đầu tiên, bubbleSort(int[] myArray) là một mặt phẳng. Nó chạy qua mảng mọi lúc. Cái thứ hai, OptimBubbleSort(int myArray[]) được tối ưu hóa bằng cách dừng thuật toán nếu vòng lặp bên trong không gây ra bất kỳ hoán đổi nào. Bộ đếm cho bạn biết bạn đã thực hiện bao nhiêu bước trong khi sắp xếp. Ở đây chúng tôi đã nhận ra Java sắp xếp bong bóng:
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)));
}
}
Kết quả của thuật toán Java sắp xếp bong bóng hoạt động:
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