插入排序的基本思想是： 每次將一個待排序的記錄按其關鍵字的大小插入到前面已排好序的文件中的適當位置， 直到全部記錄插入完為止。

一 簡介

插入排序可分為2類

本文介紹 直接插入排序
它的基本操作是： 假設待排充序的記錄存儲在數組 R[1…n] 中， 在排序過程的某一時刻， R被劃分成兩個子區間， R[1…i-1] 和 R[i…n], 其中前一個為已排序的有序區， 后一個為無序區， 開始時有序區中只含有一個元素 R[1], 無序區為 R[2…n] .

排序過程中，只需要每次從無序區中取出第一個元素， 把它插入到有序區的適當位置， 使之成為新的有序區， 依次這樣經過 $n?1$ 次插入后， 無序區為空， 有序區中包含了全部 $n$ 個元素， 至此排序完畢。

以java為例， 看一個demo.

import java.util.Arrays;/*** 2024.2.19* 插入排序*/
public class InsertSort {public static void main(String[] args) {Integer[] array_ = new Integer[]{30,45,10,30,50};System.out.println("初始順序\n"+ Arrays.toString(array_));insertSort(array_);System.out.println("最后順序\n"+Arrays.toString(array_));}static void insertSort(Integer[] array){for(int i=1; i<array.length; i++){    //第0位 獨自作為有序數列， 從1開始， 說明第二部分從第二個元素操作if(array[i]<array[i-1]){       // 0~ i-1位為有序，  如果當前值 小于 前面一個值int temp = array[i];       //將當前值 賦值給 臨時變量int j = i-1;//從第i-1位向前遍歷并移位， 直到找到小于第 i 位值停止for(; j>=0 && temp < array[j]; j--) {   //j-- 說明是從后面往回走， 然后找插入位置array[j+1] = array[j];      // 將記錄后移一位}array[j+1] = temp;      // 將基準插入到正確位置}}}
}

程序運行結果:

二 原理

直接插入排序算法 有兩重循環， 外循環表示要進行 $n?1$趟排序， 內循環表明完成一趟排序所進行的記錄間的比較和記錄的后移。 在每一趟排序中， 最多可能進行 i 次比較， 移動 $i+1$ 個記錄(后循環前后作兩次移動)

所以在最壞的情況下(反序) ， 插入排序的關鍵字之間比較次數和記錄移動次數達最大值。

最大比較次數: $C_{max}={\sum }_{i=2}^n=\frac{(n+2)(n?1)}{2}$

最大移動次數: $M_{max}={\sum }_{i=2}^n(i?1)=\frac{(n+4)(n?1)}{2}$

三 時間復雜度和空間復雜度

由上述分析可知， 當原始數組的初始狀態不同時， 直接插入排序算法的時間復雜度有很大差別， 最好的情況是數組初始為正序即升序， 此時的時間復雜度為 $O(n)$.

最壞的情況是數組初始狀態為反序， 此時的時間復雜度為 $O(n^2)$ .

容易證明該算法的平均時間復雜度也為 $O(n^2)$. 這時因為對當前無序區 $R[\mathrm{2..}i?1](2?i?n)$, 平均比較次數為 $(i?1)/2$,所以總的比較和移動次數約為 $n(n?1)/4\approx \frac{n^2}{4}$.

該算法的空間復雜度 $S(n)為O(1)$

注意概念: 若排序算法所需要的額外空間相對于輸入數據量來說是一個常數， 則稱該排序為就地排序。
直接插入排序是一個就地排序。