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) 
Lệnh cin và cout trong C++ 
Random trong Python: Tạo số random ngẫu nhiên 
ComboBox - ListBox trong lập trình C# winforms 
Thuật toán kiếm tra số nguyên tố 
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 chèn trong Java, bài toán Insertion Sort Java
Trong bài này freetuts sẽ giới thiệu đến các bạn thuật toán sắp xếp chèn (Insertion Sort). Đây là một trong những thuật toán sắp xếp căn bản trong Java.
Chúng ta sẽ cùng nhau tìm hiểu thuật toán sắp xếp chèn là gì và cách triển khai nó như thế nào trong Java. Ở cuối bài viết mình sẽ thực hành một bài tập đơn giản áp dụng thuật toán để các bạn dễ hiểu hơn.
Thuật toán sắp xếp chèn trong Java
Thuật toán sắp xếp chèn (Insertion Sort) trong Java là một trong những thuật toán sắp xếp đơn giản và phổ biến nhất trong lập trình. Thuật toán này hoạt động bằng cách chèn lần lượt các phần tử vào vị trí đúng của mình trong mảng.
Thuật toán sắp xếp chèn trong Java được phân loại là thuật toán sắp xếp trực tiếp, nghĩa là chúng ta sắp xếp trực tiếp các phần tử trong mảng. Thuật toán hoạt động bằng cách duyệt qua từng phần tử của mảng và chèn nó vào vị trí đúng của nó trong phần đã được sắp xếp.
Bài viết này được đăng tại [free tuts .net]
Cụ thể, thuật toán sắp xếp chèn hoạt động như sau:
- Bước 1: Duyệt từng phần tử trong mảng, bắt đầu từ phần tử thứ hai.
- Bước 2: So sánh phần tử hiện tại với các phần tử trước đó trong mảng.
- Bước 3: Nếu phần tử hiện tại nhỏ hơn phần tử đang xét, hoán đổi vị trí của chúng.
- Bước 4: Tiếp tục so sánh và hoán đổi vị trí cho đến khi phần tử hiện tại đứng đúng vị trí của nó trong mảng đã được sắp xếp.
- Bước 5: Lặp lại quá trình trên với các phần tử còn lại của mảng.
Đánh giá thuật toán sắp xếp chèn 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)
Vừa rồi chúng ta vừa tìm hiểu qua khái niệm thuật toán sắp xếp chèn và cách thức hoạt động của thuật toán sắp xếp chèn trong Java. Bây giờ hãy cùng freetuts tìm hiểu cách thức triển khai của nó.
Ví dụ thuật toán sắp xếp Chèn trong Java
Trong ví dụ trên chúng ta thấy:
- Hàng đầu tiên mô phỏng trạng thái ban đầu của mảng(dãy số chưa sắp xếp).
- Từ hàng thứ 2 trở đi, ta tìm chèn số đang xét vào vị trí thích hợp để đảm bảo dãy số vẫn tăng dần.
- Và khi lặp hết tất cả các số trong mảng, ta có trạng thái đã sắp xếp ở hàng cuối cùng.
Như vậy, có thể thấy cách thức hoạt động của thuật toán sắp xếp chèn trong Java khá dễ hiểu và dễ triển khai.
Chương trình triển khai thuật toán sắp xếp chèn trong Java
Dưới đây là đoạn code minh họa ví dụ trên:
/**
* Học lập trình Java miễn phí tại freetuts.net
*
* @author freetuts
*/
import java.util.Arrays;
public class InsertionSort {
public static void sort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
public static void main(String[] args) {
int[] arr = {4, 3, 2, 10, 12, 1, 5, 6};
sort(arr);
System.out.println("Học lập trình Java miễn phí tại freetuts.net");
System.out.println("Mảng sau khi được sắp xếp là: ");
System.out.println(Arrays.toString(arr));
}
}Kết quả:
Học lập trình Java miễn phí tại freetuts.net Mảng sau khi được sắp xếp là: [1, 2, 3, 4, 5, 6, 10, 12]
Qua bài này, freetuts đã giới thiệu cho các bạn về thuật toán sắp xếp chèn và cách triển khai thuật toán trong Java một cách dễ hiểu nhất, giúp các bạn có thể hiểu và áp dụng vào các bài toán khó và phức tạp hơn trong Java. Chúc các bạn thành công.
