408答疑

---

---

二、插入排序

基本概念

• 定義：插入排序是一種簡單直觀的排序算法，其基本思想是每次將一個待排序的記錄按其關鍵字大小插入前面已排好序的子序列，直到全部記錄插入完成。

插入排序方法

• 直接插入排序：將待排元素往已排序好的序列進行插入，叫做直接插入排序。

• 折半插入排序：由插入排序的思想可以引申出折半插入排序。

• 希爾排序：由插入排序的思想可以引申出希爾排序。

直接插入排序

算法描述

• 基本思想：直接插入排序是一種最簡單也最直觀的排序算法。其基本思想是每次將一個待排序的記錄按其關鍵字大小插入前面已排好序的子序列，直到全部記錄插入完成。

• 操作步驟：要將元素 $L(i)$ 插入已有序的子序列 $L[\mathrm{1...}i?1]$，需要執行以下操作（下面用 $L[]$ 表示一個表，而用 $L()$ 表示一個元素）：

  1. 查找出 $L(i)$ 在 $L[\mathrm{1...}i?1]$ 中的插入位置 $k$。
  2. 將 $L[k...i?1]$ 中的所有元素依次后移一個位置。
  3. 將 $L(i)$ 復制到 $L(k)$。

• 實現過程：為了實現對 $L[\mathrm{1...}n]$ 的排序，可以將 $L(2)$ ～$L(n)$ 依次插入前面已排好序的子序列，初始 $L[1]$ 可以視為一個已排好序的子序列。

• 執行次數：共進行 $n?1$ 次插入操作（從 $L(2)$ 到 $L(n)$）。

• 原地排序：僅需常數級輔助空間，空間復雜度為 $O(1)$。

示例

• 初始序列： $49_1,38,65,97,76,13,27,49_2$。

• 排序過程：
  初始時 49 可以視為一個已排好序的子序列，按照上述算法進行直接插入排序的過程如下圖所示，括號內是已排好序的子序列。

性能分析

• 空間效率：僅使用了常數個輔助單元，因而空間復雜度為 $O(1)$。

• 時間效率：

  • 在排序過程中，向有序子表中逐個地插入元素的操作進行了 $n?1$ 趟，每趟操作都分為比較關鍵字和移動元素，而比較次數和移動次數取決于待排序表的初始狀態。
  • 在最好情況下，表中元素已經有序，此時每插入一個元素，都只需比較一次而不用移動元素，因而時間復雜度為 $O(n)$。
  • 在最壞情況下，表中元素順序剛好與排序結果中的元素順序相反（逆序），總的比較次數達到最大，總的移動次數也達到最大，總的時間復雜度為 $O(n^2)$。
  • 平均情況下，考慮待排序表中元素是隨機的，此時可以取上述最好與最壞情況的平均值作為平均情況下的時間復雜度，總的比較次數與總的移動次數約為 $n^2/4$。
  • 因此，直接插入排序算法的時間復雜度為 $O(n^2)$。

• 穩定性：因為每次插入元素時總是從后往前先比較再移動，所以不會出現相同元素相對位置發生變化的情況，即直接插入排序是一個穩定的排序算法。

• 適用性：直接插入排序適用于順序存儲和鏈式存儲的線性表，采用鏈式存儲時無須移動元素。

折半插入排序

改進點

• 折半插入排序算法對直接插入排序算法進行了改進，主要在于查找待插入元素位置的方法。通過使用折半查找來確定待插入元素的位置，從而減少比較次數。

算法步驟

1. 將待插入的元素暫存到數組的第一個位置。
2. 使用折半查找確定該元素在已排序子序列中的正確位置。
3. 從后向前移動元素，為新元素騰出空間。
4. 將新元素插入到正確的位置。

性能分析

• 時間復雜度：折半插入排序的時間復雜度約為 $O(n{\log }_{2}n)$，這是因為折半查找減少了比較元素的次數。然而，由于元素的移動次數并未改變，總的時間復雜度仍為 $O(n^2)$。對于數據量不大的排序表，折半插入排序往往能表現出很好的性能。

• 穩定性：折半插入排序是一種穩定的排序算法，因為它在插入元素時總是從后往前先比較再移動，不會出現相同元素相對位置發生變化的情況。

• 適用性：折半插入排序僅適用于順序存儲的線性表，因為它依賴于順序存儲的線性結構來實現折半查找和元素的移動。

希爾排序

相關概念

• 基本思想：希爾排序是基于直接插入排序進行改進而得來，又稱縮小增量排序。它更適用于基本有序的排序表和數據量不大的排序表。

• 排序過程：先將待排序表分割成若干形如 $L[i,i+d,i+2d,?,i+kd]$ 的“特殊”子表，即相隔某個“增量”的記錄組成一個子表，對各個子表分別進行直接插入排序，當整個表中的元素已呈“基本有序”時，再對全體記錄進行一次直接插入排序。

• 增量選擇：先取一個小于 $n$ 的增量 $d_1$，把表中的全部記錄分成 $d_1$ 組，所有距離為 $d_1$ 的倍數的記錄放在同一組，在各組內進行直接插入排序；然后取第二個增量 $d_2<d_1$，重復上述過程，直到所取到的 $d_i=1$，即所有記錄已放在同一組中，再進行直接插入排序，由于此時已經具有較好的局部有序性，因此可以很快得到最終結果。

• 穩定性：當相同關鍵字的記錄被劃分到不同的子表時，可能會改變它們之間的相對次序，因此希爾排序是一種不穩定的排序算法。

• 適用性：希爾排序僅適用于順序存儲的線性表。

示例分析

希爾排序的效率

效率分析

• 希爾排序的效率很高，盡管它也屬于插入排序的一種，但其高效的原因有兩個：
  1. 對于直接插入排序來說，數據量越小，效率越高。
  2. 對于直接插入排序來說，數據基本有序時，效率越高。

空間復雜度

• 僅使用了常數個輔助單元，因此空間復雜度為 $O(1)$。

時間復雜度

• 增量序列的影響：希爾排序的時間復雜度依賴于所取“增量”序列的函數，這涉及一些數學上尚未解決的難題。

• 特定情況下的時間復雜度： 當增量序列為 $dlta[k]=2^{t?k+1}?1$ 時，希爾排序的時間復雜度為 $O(n^{3/2})$，其中 $t$ 為排序趟數，$1\le k\le t\le ?{\log }_2(n+1)?$。

• 實驗基礎上的推論：在大量的實驗基礎上推出：當 $n$ 在某個特定范圍內，希爾排序所需的比較和移動次數約為 $n^{1.3}$，當 $n\to \infty$ 時，可減少到 $n({\log }_{2}n{)}^{2^{[2]}}$。

• 最壞情況：在最壞情況下希爾排序的時間復雜度為 $O(n^2)$。

九、參考資料

鮑魚科技課件

b站免費王道課后題講解:

網課全程班:

26王道考研書