插入排序

上節(jié)課我們學(xué)習(xí)了一個(gè)經(jīng)典的排序算法—冒泡排序，本節(jié)我們來聊一下基礎(chǔ)排序中的插入排序算法。

1. 插入排序算法原理

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

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

下面我們用一個(gè)簡(jiǎn)單的圖片描述下插入排序的過程，如下所示。

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

3. 插入排序算法的 Python 實(shí)現(xiàn)

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

• 對(duì)于插入排序找到元素的插入位置，有沒有可能利用有序的規(guī)律進(jìn)一步優(yōu)化算法？
• 插入排序的列表是鏈?zhǔn)降臄?shù)據(jù)結(jié)構(gòu)，我們是不是可以省掉移動(dòng)元素這樣一個(gè)比較耗時(shí)的部分？

我們現(xiàn)在分別實(shí)現(xiàn)3種情況下的插入排序算法：

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

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，繼續(xù)向前，直到找到小于等于t的數(shù)
            if nums[j] <= t:
                k = k + 1
                break
            # 每次找到的nums[j]大于t，則將當(dāng)前值想向移動(dòng)一位
            nums[j + 1] = nums[j]
        # 此時(shí)找到t的位置，并將t放到對(duì)應(yīng)位置
        nums[k] = t
    return True 

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

4. 插入排序算法的優(yōu)化

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

4.1 使用二分法的插入排序

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

5       8       10       12     17     20       25      26

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

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

>>> 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() 方法又給了一個(gè)別名，就是 bisect：

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

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

from bisect import bisect

def insert_sort2(nums):
    """
    插入排序: 使用二分法實(shí)現(xiàn)元素快速插入
    """
    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 

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

4.2 基于鏈表的插入排序

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

我們就來實(shí)現(xiàn)一下這個(gè)基于鏈表的插入排序算法。首先是要分析鏈表插入的思路，來看初始的狀態(tài)：

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

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

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

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

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

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:
            # 針對(duì)于第一次，第一個(gè)元素直接掛到sorted_head后即可
            sorted_head.next = ListNode(p.val)
        else:
            find = False
            while cur:
                if p.val > cur.val:
                    # 插入節(jié)點(diǎn)值大于當(dāng)前指向的節(jié)點(diǎn)值，將cur和prev之后后移一位再比較
                    cur = cur.next
                    prev = prev.next
                else:
                    # 當(dāng)前節(jié)點(diǎn)值大于插入元素的值，在此執(zhí)行插入操作然后退出循環(huán)
                    insert_data = ListNode(p.val)
                    prev.next = insert_data
                    insert_data.next = cur
                    find = True
                    break
            # 對(duì)于大于所有的值，需要插入到有序鏈表的末尾
            if not find:
                prev.next = ListNode(p.val)
            
        p = p.next
    return sorted_head.next

最后這個(gè)在 leetcode 上有一道對(duì)應(yīng)的編程題，題號(hào)為147，難度標(biāo)記為中等。我這里的代碼并不優(yōu)秀，只是看起來比較簡(jiǎn)單明了，額外用了許多空間。大家有興趣的話可以優(yōu)化下代碼，實(shí)現(xiàn)在原鏈表的基礎(chǔ)上完成插入排序。

5. 小結(jié)

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

Tips：文中動(dòng)圖制作參考：https://visualgo.net/zh/sorting。