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