Các kiểu dữ liệu trong C ( int - float - double - char ...) 
Thuật toán tìm ước chung lớn nhất trong C/C++ 
Cấu trúc lệnh switch case trong C++ (có bài tập thực hành) 
ComboBox - ListBox trong lập trình C# winforms 
Random trong Python: Tạo số random ngẫu nhiên 
Lệnh cin và cout trong C++ 
Cách khai báo biến trong PHP, các loại biến thường gặp 
Download và cài đặt Vertrigo Server 
Thẻ li trong HTML 
Thẻ article trong HTML5 
Cấu trúc HTML5: Cách tạo template HTML5 đầu tiên 
Cách dùng thẻ img trong HTML và các thuộc tính của img 
Thẻ a trong HTML và các thuộc tính của thẻ a thường dùng Thuật toán sắp xếp nổi bọt trong Java, (Bubble Sort) và áp dụng trong Java
Trong bài này, freetuts sẽ cùng các bạn tìm hiểu về thuật toán sắp xếp nổi bọt (Bubble Sort) trong Java và cách triển khai thuật toán vào các bài toán trong Java. Đây là 1 một trong những thuật toán kinh điển và áp dụng rất nhiều trong kỹ thuật lập trình, các bạn cố gắng theo dõi nhé!
Thuật toán sắp xếp nổi bọt trong Java
Thuật toán sắp xếp nổi bọt trong Java là thuật toán thực hiện sắp xếp dãy số bằng cách lặp lại công việc đổi chỗ 2 số liên tiếp nhau nếu chúng đứng sai thứ tự(số sau bé hơn số trước với trường hợp sắp xếp tăng dần) cho đến khi dãy số được sắp xếp.
Giả sử chúng ta cần sắp xếp dãy số [5 1 4 2 8] này tăng dần.
Lần lặp đầu tiên:
( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Ở đây, thuật toán sẽ so sánh hai phần tử đầu tiên, và đổi chỗ cho nhau do 5 > 1.
( 1 5 4 2 8 ) –> ( 1 4 5 2 8 ), Đổi chỗ do 5 > 4
( 1 4 5 2 8 ) –> ( 1 4 2 5 8 ), Đổi chỗ do 5 > 2
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Ở đây, hai phần tử đang xét đã đúng thứ tự (8 > 5), vậy ta không cần đổi chỗ.
Lần lặp thứ 2:
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 )
( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Đổi chỗ do 4 > 2
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
Bây giờ, dãy số đã được sắp xếp, Nhưng thuật toán của chúng ta không nhận ra điều đó ngay được. Thuật toán sẽ cần thêm một lần lặp nữa để kết luận dãy đã sắp xếp khi và khi khi nó đi từ đầu tới cuối mà không có bất kỳ lần đổi chỗ nào được thực hiện.
Lần lặp thứ 3:
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
Trên đây là ví dụ minh họa của thuật toán sắp xếp nổi bọt trong Java.
Đánh giá thuật toán sắp xếp nổi bọt trong Java
Độ phức tạp thuật toán:
- Trường hợp tốt: O(n)
- Trung bình: O(n^2)
- Trường hợp xấu: O(n^2)
- Không gian bộ nhớ sử dụng: O(1)
Thuật toán này được áp dụng cho các tập dữ liệu nhỏ, vì nó lặp hết tất cả các phần tử có trong tập dữ liệu. Điều này tốn rất nhiều thời gian, đầy là một thuật toán được xem là chậm nhất trong số các thuật toán sắp xếp.
Bài viết này được đăng tại [free tuts .net]
Code minh họa cho thuật toán sắp xếp nổi bọt trong Java
Sau đây là đoạn code Java minh họa cho ví dụ trên:
/**
* Học lập trình Java miễn phí tại freetuts.net
*
* @author freetuts
*/
public class BubbleSort {
public static void main(String[] args) {
int[] arr = {5, 1, 4, 2, 8};
System.out.println("Học lập trình Java miễn phí tại freetuts.net");
System.out.println("Dãy số trước khi sắp xếp:");
printArray(arr);
bubbleSort(arr);
System.out.println("\nDãy số sau khi sắp xếp:");
printArray(arr);
}
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// hoán đổi 2 phần tử
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
public static void printArray(int[] arr) {
int n = arr.length;
for (int i = 0; i < n; ++i) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
Kết quả:
Học lập trình Java miễn phí tại freetuts.net Dãy số trước khi sắp xếp: 5 1 4 2 8 Dãy số sau khi sắp xếp: 1 2 4 5 8
Vậy freetuts đã giới thiệu cho bạn thuật toán sắp xếp nổi bọt và cách triển khai thuật toán này bằng ngôn ngữ Java. Đây là một thuật toán kinh điển được đánh giá dễ nhất trong các thuật toán sắp xếp kinh điển. Các bạn hãy thử tự triển khai thuật toán này theo ví dụ trên để hiểu hơn về thuật toán này nhé.
Chúc các bạn thực hiện thành công!
