最近在看riscv手冊的時候，里面有一段代碼是插入排序，但是單看代碼的時候有點迷，沒看懂咋操作的，后來又查資料復習了一下，最終才把代碼看明白，所以寫篇博客記錄一下。

插入排序像打撲克牌

這是我聽到過比較形象的一個比喻。在打撲克牌的時候，我們是一張一張去摸牌，然后將牌按照某種自己定義的順序進行排序。下面我來類比一下：

• 從牌堆頂將要摸取的10張牌? <->? 待排序數組
• 一張一張摸牌? <->? 一個數一個數進行排序
• 牌要么在牌堆中，要么在手中；數要么在待排序子數組中，要么在已排序子數組中
• 在牌堆中的牌加上在手中的牌是所有牌；在待排序子數組中的數加上在已排序子數組中的數是所有數（換句話說 我們將所有牌（數）分為了牌堆牌（待排序數組）和手中牌（已排序數組）兩部分）
• 初始狀態：手中無牌（已排序數組為空），牌（數）全在牌堆（待排序數組）中
• 依次從牌堆（待排序數組）中取牌（數），拿取到的牌（數）與手中的最大的牌進行比較，如果大于，則直接放在手的最右邊，否則就和次大的牌進行比較，直到找到這張牌的位置（不再進行具體的類比替換）
• 直到牌堆中無牌，手中牌為排好序的牌

其實我咋說，都說不清，如果打牌的話，自己類比一下，會發現特別有意思。即使是a[j] = a[j-1]這一步，在摸牌時也有對應。下面我解釋一下這行碼。

比如說，我的手只能放10張牌，并且摸得牌都是從左到右以此放在我手上，所以我在比較大小的時候，如果這個牌比手里當前比較的牌小時，我會把手里當前比較的牌往后挪一下，給剛摸得牌放的空間。（我說的比較抽象 感覺還是需要想象 如果沒打過撲克 可能不太好理解我在說啥）??

下面放一段正兒八經的插入排序的說明吧。

?插入排序是一種簡單而有效的排序算法，它的基本思想是將一個元素插入到已經有序的序列中，從而得到一個新的、元素個數增加的有序序列。插入排序的過程可以類比于打撲克牌時，將摸到的牌按照大小順序插入到手中的牌中。插入排序的平均時間復雜度是 O(n^2)，空間復雜度是 O(1)。下面我用一些例子來詳細解釋插入排序的原理和步驟。

假設我們有一個數組 [6, 7, 9, 3, 1, 5, 4, 8]，我們要對它進行升序排序。我們可以用以下的方法進行插入排序：

• 首先，我們將數組的第一個元素 6 看作是一個已經有序的序列，將剩余的元素看作是未排序的序列。
• 然后，我們從未排序的序列中取出第一個元素 7，與已排序的序列中的元素從后往前依次比較，如果 7 大于或等于已排序的元素，則將 7 插入到該元素的后面，否則繼續比較。在這個例子中，7 大于 6，所以我們將 7 插入到 6 的后面，得到新的有序序列 [6, 7]，未排序序列為 [9, 3, 1, 5, 4, 8]。
• 接著，我們從未排序的序列中取出第一個元素 9，與已排序的序列中的元素從后往前依次比較，如果 9 大于或等于已排序的元素，則將 9 插入到該元素的后面，否則繼續比較。在這個例子中，9 大于 7 和 6，所以我們將 9 插入到 7 的后面，得到新的有序序列 [6, 7, 9]，未排序序列為 [3, 1, 5, 4, 8]。
• 依此類推，我們每次從未排序的序列中取出第一個元素，與已排序的序列中的元素從后往前依次比較，找到合適的位置插入，直到未排序的序列為空，排序完成。最終的有序序列為 [1, 3, 4, 5, 6, 7, 8, 9]。