大家好！今天我們來聊聊一個簡單卻非常經典的排序算法——插入排序（Insertion Sort）。在所有的排序算法中，插入排序是最直觀的一個。
一、插入排序的基本思想
插入排序的核心思想是：將一個待排序的元素，插入到已排好序的部分中，使得插入后的部分依然是有序的。
具體來說，插入排序會從數組的第二個元素開始，逐步與前面的元素進行比較，并將其插入到合適的位置，直到整個數組都排序完成。
舉個例子：
- 假設我們有一個數組
[5, 3, 8, 4, 2]，我們從第二個元素開始，逐個與前面的元素進行比較。 - 第一次比較，我們將
3與5比較，發現3小于5，就將3插入到5的前面，數組變成[3, 5, 8, 4, 2]。 - 第二次比較，將
8與前面的元素逐一比較，發現它已經大于5，不需要移動。 - 繼續這個過程，直到整個數組都變得有序。
二、插入排序的步驟
- 從第二個元素開始遍歷，逐個元素插入到已排好序的部分。
- 對于每個元素，向前比較，直到找到合適的位置為止。
- 插入的操作可以通過移動元素的位置來完成，使得原來位置較大的元素騰出位置來插入新的元素。
三、插入排序的實現
我們通過 Java 來實現插入排序，看看這個過程是如何完成的。
public static void InsertSort(int[] arr) {//i待插入數據下標for (int i = 1; i < arr.length; i++) {//j為已排序部分最后一個元素，即待排序元素的前一個元素，使j與j+1比較，j大交換，j小結束for (int j = i - 1; j >= 0; j--) {if (arr[j] > arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;} else{break;}}}}四、插入排序的時間復雜度
插入排序的時間復雜度主要取決于待排序數據的順序。
-
最優情況：當數組已經是有序的時，內層循環不會執行任何移動操作，因此時間復雜度是 O(n)，其中
n是數組的長度。 -
最壞情況：當數組是逆序時，每次插入都需要將元素移動到數組的前面，這時內層循環會執行
i次移動操作。因此時間復雜度是 O(n2)。 -
平均情況：假設元素是隨機排列的，平均情況下，時間復雜度也為 O(n2)。
五、插入排序的優缺點
優點：
- 簡單直觀：插入排序的實現非常簡單，而且非常適合小規模數據的排序。
- 穩定性：插入排序是穩定的排序算法，即相等的元素不會交換位置。
- 適用于部分有序的數組：當數組已經接近有序時，插入排序會表現得非常高效。
缺點：
- 時間復雜度高：在數據規模較大的時候，插入排序的效率較低，特別是在最壞情況下，時間復雜度達到 O(n2)。
- 不適合大規模數據：對于大數據量的排序，插入排序不是最優選擇。其他更高效的排序算法（如快速排序、歸并排序）通常會更適用。
六、插入排序的應用場景
盡管插入排序在大規模數據中效率較低，但在一些特殊場景下，它依然非常有用：
- 小規模數據排序：在數據量較小的情況下，插入排序非常高效且簡單。
- 部分有序的數組：如果數據已經部分有序，插入排序可以大大減少排序的工作量。
- 在線算法：插入排序是一種在線算法，也就是說它可以逐步地接收新的數據并進行排序。例如在實時排序數據流時，可以使用插入排序。
