簡介

在本博客中，我們將學習插入排序的工作原理。插入排序是一種簡單的排序算法，它通過一次一個元素構建最終的排序數組。對于小型數據集，它的效率較高，并且常作為更復雜排序算法的一部分使用。

插入排序的工作原理

• 從數組的第二個元素開始。
• 將其與前面的元素進行比較。
• 如果較小，則將較大的元素向右移動。
• 將該元素插入到正確的位置。
• 對所有元素重復上述步驟。

import java.util.Arrays;
public class InsertionSortExample {
    public static void insertionSort(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 = {64, 34, 25, 12, 22, 11, 90};
        insertionSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

時間復雜度

• 最佳情況：O(n)，當數組已經排序時。
• 平均和最壞情況：O(n²)。

空間復雜度

• O(1)，因為它在原地排序。

優點

• 實現簡單
• 對于小型數據集效率高
• 自適應（對于部分排序的數組高效）。

缺點

• 對于大型數據集效率低。

總結

插入排序在數據幾乎已排序或排序小型數組的場景中表現良好。它的簡單性使其成為教育目的和作為更復雜算法的構建塊的良好選擇。

若你想提升Java技能，可關注我們的Java培訓課程。