卫浴网站怎么做,网站为契机建设校园数字化,源码论坛网站,wordpress 登录页面最近在看riscv手册的时候#xff0c;里面有一段代码是插入排序#xff0c;但是单看代码的时候有点迷#xff0c;没看懂咋操作的#xff0c;后来又查资料复习了一下#xff0c;最终才把代码看明白#xff0c;所以写篇博客记录一下。 插入排序像打扑克牌 这是我听到过比较形…最近在看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]。
