了解插入排序演算法（附Java範例）

插入排序是一種迭代排序演算法。它透過將每個未排序的元素插入到已排序子數組中的正確位置來建立一個已排序子數組，一次一個元素。 想像對一手撲克牌進行排序 - 從一張已排序的牌開始，然後將後續的每張牌插入已排序的牌中的正確位置。

插入排序如何運作

讓我們用一個要按升序排序的範例陣列來說明：

第一次迭代：

我們認為第一個元素已經排序。 演算法從第二個元素開始。

比較 2 和 8，因為 2

第二次迭代：

我們將 6 與排序後的子數組 (2, 8) 進行比較。 6＜ 8，所以 8 右移。 那麼，由於 6 > 2, 6 位於 2 的右側。

此過程將持續進行，直到整個陣列完成排序。

Java 中的實作

<code class="language-java">import java.util.Arrays;

public class InsertionSortTest {
    public static void main(String[] args) {
        int[] arr = {8, 2, 6, 4, 9, 1};
        System.out.println("Unsorted array: " + Arrays.toString(arr));
        insertionSort(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }

    public static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; 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;
        }
    }
}</code>

程式碼進行迭代，將每個元素作為 key。 然後，它將 key 與已排序部分中的元素進行比較，將較大的元素向右移動，直到找到 key 的正確位置。

例如，在第二次迭代中（i=2）：

key 為 6。 while 循環移動元素，直到找到正確的位置：

最後插入6：

輸出：

未排序數組：[8,2,6,4,9,1] 排序數組：[1, 2, 4, 6, 8, 9]

複雜性分析

• 時間複雜度：
  • 最佳情況 (O(n))：已經排序的陣列。
  • 平均情況 (O(n²))：隨機排列的元素。
  • 最壞情況 (O(n²))：逆序數組。
• 空間複雜度：O(1)（就地演算法）

結論

插入排序的二次時間複雜度使其對於大型資料集效率低下。 然而，它是一個簡單的演算法，並且在小數據集或接近排序的數據上表現良好。

以上是了解插入排序演算法（附Java範例）的詳細內容。更多資訊請關注PHP中文網其他相關文章！