Thuật toán sắp xếp Insertion Sort trong Java

Thuật toán sắp xếp Insertion Sort là một thuật toán sắp xếp trực tiếp, tức là sắp xếp từng phần tử một. Thuật toán này hoạt động bằng cách lấy phần tử đầu tiên của mảng và chèn nó vào đúng vị trí của nó trong danh sách được sắp xếp. Sau đó, nó tiếp tục lấy phần tử thứ hai và chèn nó vào đúng vị trí của nó trong danh sách đã sắp xếp và tiếp tục như vậy cho tới khi danh sách được sắp xếp hoàn chỉnh.

Thuật toán Insertion Sort có hiệu quả khi sắp xếp các mảng có số lượng phần tử nhỏ. Tuy nhiên, nó không hiệu quả khi sắp xếp các mảng có kích thước lớn.

Dưới đây là mã nguồn minh họa cho thuật toán sắp xếp Insertion Sort trong Java:

public class InsertionSort {
    public static void main(String[] args) {
        int[] arr = { 5, 2, 8, 3, 9, 1 };
        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 = j - 1;
            }
            arr[j + 1] = key;
        }
        System.out.println("Sorted array:");
        for (int i = 0; i < n; ++i) {
            System.out.print(arr[i] + " ");
        }
    }
}