插入排序的簡單理解

• 2022 年 6 月 20 日
• 筆記
• 排序, 數據結構與算法, 算法

詳細描述

插入排序的基本思想是：將一個記錄插入到已經排好序的有序表中，從而得到一個新的、記錄數增 1 的有序表。

在其實現過程中使用雙層循環，外層循環針對除了第一個元素之外的所有元素，內層循環針對當前元素前面的有序表進行待插入位置查找，並進行移動。

選擇排序詳細的執行步驟如下：

1. 從第一個元素開始，該元素可以認為已經被排序；
2. 取出下一個元素，在已經排序的元素序列中從後向前掃描；
3. 如果該元素（已排序）大於新元素，將該元素移到下一位置；
4. 重複步驟 3，直到找到已排序的元素小於或者等於新元素的位置；
5. 將新元素插入到該位置；
6. 重複步驟 2~5。

算法圖解

問題解疑

插入排序是原地排序算法嗎？

插入排序算法的運行並不需要額外的存儲空間，所以空間複雜度是 \(O(1)\)，也就是說，這是一個原地排序算法。

插入排序是穩定的排序算法嗎？

對於值相同的元素，可以選擇將後面出現的元素，插入到前面出現元素的後面，這樣就可以保持原有的前後順序不變，所以插入排序是穩定的排序算法。

插入排序的時間複雜度是多少？

最好情況時間複雜度為 \(O(n)\)；最壞情況時間複雜度為 \(O(n^2)\)；平均時間複雜度為 \(O(n^2)\)。

代碼實現

package cn.fatedeity.algorithm.sort;

/**
 * 插入排序算法
 */
public class InsertionSort {
    private static void swap(int[] numbers, int src, int target) {
        int temp = numbers[src];
        numbers[src] = numbers[target];
        numbers[target] = temp;
    }

    public static int[] sort(int[] numbers) {
        for (int i = 1; i < numbers.length; i++) {
            for (int j = i; j > 0; j--) {
                if (numbers[j - 1] <= numbers[j]) {
                    break;
                }
                swap(numbers, j, j - 1);
            }
        }
        return numbers;
    }
}