插入排序

上節課我們學習了一個經典的排序算法—冒泡排序，本節我們來聊一下基礎排序中的插入排序算法。

1. 插入排序算法原理

插入排序的基本思想是：將整個數組 nums 分為有序和無序的兩個部分。前者在左邊，后者在右邊。最開始有序的部分只有第一個元素，其余都屬于無序的部分。每次取出無序部分的第一個(最左邊)元素，把它加入有序部分。通過比較找到屬于該元素的位置 k，然后將原 k 位置及其后面的有序部分元素都向右移動一個位置，有序的部分即增加了一個元素，無序部分減少了一個元素。這樣一直繼續下去，直到無序的部分沒有元素，整個插入排序就算完成。

2. 插入排序算法過程分析

下面我們用一個簡單的圖片描述下插入排序的過程，如下所示。

從上面的過程我們可以看到，比較關鍵的一步就是找到準備插入元素的位置。簡單點的話，可以從有序部分的最后開始往前依次比較。若有序元素比該插入值大則該有序元素后退一個位置，然后繼續向前比較，直到有序列表中的元素小于該插入值。

3. 插入排序算法的 Python 實現

看到前面的插入算法的思路有沒有躍躍欲試，想趕緊把它寫出來的沖動？先別急，我們先思考幾個問題：

• 對于插入排序找到元素的插入位置，有沒有可能利用有序的規律進一步優化算法？
• 插入排序的列表是鏈式的數據結構，我們是不是可以省掉移動元素這樣一個比較耗時的部分？

我們現在分別實現3種情況下的插入排序算法：

• 普通的插入排序，從有序列表的最后依次往前查找插入元素的位置；
• 改進的插入排序，對于查找插入元素位置改為使用二分查找方法，然后統一移動插入元素后面的所有元素；
• 鏈表元素的插入排序；

3.1 普通的插入排序

我們直接看代碼：

def insert_sort(nums):
    """
    插入排序
    """
    if not nums:
        return False
    for i in range(1, len(nums)):
        t = nums[i]
        # 從i-1位置開始往前找
        for j in range(i - 1, -1, -1):
            k = j
            # 如果nums[j]大于t，繼續向前，直到找到小于等于t的數
            if nums[j] <= t:
                k = k + 1
                break
            # 每次找到的nums[j]大于t，則將當前值想向移動一位
            nums[j + 1] = nums[j]
        # 此時找到t的位置，并將t放到對應位置
        nums[k] = t
    return True 

看上面的代碼，第二個 for 循環便是從有序列表的最后一個元素開始和待插入值進行比較，并逐步向前移動比較，一但待插入值大于或等于當前值，那么待插入值就在該值的后面位置插入；否則將當前位置的值向后移動一位，給待插入值騰出空間 （因此插入值必須一開始先保存，如果被最后一個值給覆蓋了，該插入值就沒了）。

4. 插入排序算法的優化

從上面的內容中可以很明顯看出插入排序有一個可以優化的地方，就是插入排序中每次查找插入元素的位置時，我們可以利用前面已排好序的特點，使用二分法快速定位插入元素位置，這樣會比從后向前一個一個比較要高效許多，特別是在排序規模較大時，尤為明顯。

4.1 使用二分法的插入排序

二分法查找是一種非常高效的搜索方法，主要原理是每次搜索可以拋棄一半的值來縮小范圍。其時間復雜度是O(log₂n)，一般用于對普通搜索方法的優化。使用二分法時一定要保證數組是排序的，例如下面的數組：

5       8       10       12     17     20       25      26

假設想查找 10 的位置，首先給個頭尾指針：first 和 end，分別指向 0 和 7 的位置。取中間數 mid = (0 + 7) / 2 = 3 ，而 nums[3] = 12 > 10，可知 10 的位置肯定在 first 和 mid 指針之間。此時我們將 end = mid，然后繼續使用前面那樣的方式在左邊數組中查找，直到最后 first >= end 為止。

在 Python 中有一個二分查找模塊：bisect，該模塊中的方法都是基于二分查找法，可以使用 bisect_right() 方法來輔助我們快速實現插入元素的定位。首先在 Python 的交互式模式下測試下該方法：

>>> from bisect import bisect_right
>>> x = [2, 3, 4, 7, 9, 12] 
>>> bisect_right(x, 5) 
3
>>> bisect_right(x, 1) 
0
>>> bisect_right(x, 13) 
6
>>> bisect_right(x, 7)  
4

可以看到，bisect_right() 方法快速返回了待插入元素在有序列表中的位置。

注意：在 bisect.py 模塊中，bisect_right() 方法又給了一個別名，就是 bisect：

# 源碼位置：lib/bisect.py
# ...
# Create aliases
bisect = bisect_right

于是我們給出基于二分法的插入排序算法：

from bisect import bisect

def insert_sort2(nums):
    """
    插入排序: 使用二分法實現元素快速插入
    """
    if not nums:
        return False
    for i in range(1, len(nums)):
        k = bisect(nums[:i], nums[i])
        nums[k], nums[k + 1: i + 1] = nums[i], nums[k:i]
    return True 

可以看到，使用了二分模塊之后，插入排序算法的代碼變得非常簡潔，而且也相比原來的代碼高效了不少。大家可以把排序的規模弄到萬級別上進行測試和對比，就能夠看到代碼的區別。

4.2 基于鏈表的插入排序

對于使用的鏈表結構的數據我們無法向前面那樣使用二分法進行插入位置的獲取，但這樣的鏈表結構有一個好處，就是我們找到對應的插入位置后，后面的元素不用整體后移，只需要 O(1) 的復雜度即可插入成功。

我們就來實現一下這個基于鏈表的插入排序算法。首先是要分析鏈表插入的思路，來看初始的狀態：

我們自定義一個有序鏈表的頭部 head，這樣是為了后面操作的方便。接下來每次從無序鏈表中選擇一個數據插入到有序鏈表中，首先完成初始代碼如下：

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def insertion_sort_list(head):
    # 定義一個新的有序節點
    new_sorted = ListNode(0)
    p = head
    while p:
        # 每次插入值為p.val的節點
        # ...
        # 重新指向下一個待插入的數據
        p = p.next
    return new_sorted.next

可以看到，比較核心的代碼就是對于有序鏈表，如何插入一個值并保證鏈表的有序。我們的有序鏈表插入過程如下，需要準備 prev 和 cur 兩個指針，分別表示當前比較的值的位置和上一個元素的位置，來看看插入有序鏈表的示意圖：

由于鏈表的單向性，我們需要從有序鏈表的第一個元素開始比較，直到找到元素值大于該插入節點的值，然后就需要執行插入動作。這里需要考慮兩種極端情況，一種是插入到最前面，另一種是插入到最后面。完整的鏈表插入排序算法的代碼如下(代碼中已做好詳細注釋)：

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def insert_link_sort(head):
    sorted_head = ListNode(0)
    p = head
    while p:
        prev = sorted_head
        cur = prev.next
        if not cur:
            # 針對于第一次，第一個元素直接掛到sorted_head后即可
            sorted_head.next = ListNode(p.val)
        else:
            find = False
            while cur:
                if p.val > cur.val:
                    # 插入節點值大于當前指向的節點值，將cur和prev之后后移一位再比較
                    cur = cur.next
                    prev = prev.next
                else:
                    # 當前節點值大于插入元素的值，在此執行插入操作然后退出循環
                    insert_data = ListNode(p.val)
                    prev.next = insert_data
                    insert_data.next = cur
                    find = True
                    break
            # 對于大于所有的值，需要插入到有序鏈表的末尾
            if not find:
                prev.next = ListNode(p.val)
            
        p = p.next
    return sorted_head.next

最后這個在 leetcode 上有一道對應的編程題，題號為147，難度標記為中等。我這里的代碼并不優秀，只是看起來比較簡單明了，額外用了許多空間。大家有興趣的話可以優化下代碼，實現在原鏈表的基礎上完成插入排序。

5. 小結

本小節中，我們介紹了插入排序算法的排序原理及思路，同時分別完成了3種情況的插入排序算法，特別是最后一種情況的實現，涉及到鏈表操作，大家要多多練習，掌握這些基礎的排序算法。

Tips：文中動圖制作參考：https://visualgo.net/zh/sorting。