插入排序（形象类比）

最近在看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]。