当前位置：首页 > news >正文

排序算法系列之（四）——抓扑克牌风格的插入排序

news 来源：原创 2024/5/3 19:06:46

前言

上次聊到了快速排序，我们说到快排这个名字是非常抽象的，究竟什么是快排，从名字上我们无从得知，或许叫二分排序都比快速排序要形象的多，可是这又和归并排序重复了，所以我们还是不要在意快排的名字了，接下来看一下今天的插入排序，这里指的是简单的插入排序。

插入排序相比于快速排序要形象很多，整个排序过程就是在不断的插入操作中完成的，如果你打过扑克基本上很容易理解这种排序方法，排序的过程几乎与抓扑克牌的过程一模一样，假设三个人斗地主，每人一张牌依次抓取，其实一旦开始抓一张牌，那么牌堆里哪些牌是你的就已经确定了，只不过是隔两张之后的那张就是你的，所有这些归属于你的牌在牌堆里的顺序就是这些牌的初始顺序，而你抓牌摆牌的过程就是给这些牌从小到大（当然可以从大到小）排序的过程。

插入排序

整个排序过程可以使用抓牌来模拟，抓第一张牌的时候无所谓顺序，放在手里就好，抓第二张牌的时候和第一张比较，按从小到大排好顺序，抓第三张牌的时候，和前面两张比较，“插入”适当的位置，后面的牌依次类推插入正确位置，最后手里的牌也就排好了顺序，还有一点需要注意，抓牌时可以真的将一张牌插入到另外两张牌之间的（实际上也是占用了原来牌的位置），但是在内存中，比如连续下标的一个数组中，要想在元素2和元素3中间插入一个数字是做不到的，如果确实要放到这两个数中间，那就需要将元素3往后移动，给需要插入的这个数字腾出一个地方，元素3后面如果也有其他元素呢？那就也需要向后移动，一直到后面没有需要移动的元素为止。

想象一下完整的抓牌过程，其中的关键点就在于拿到一张新牌（元素）后，和之前有序的手牌进行比较，找到合适的插入位置，依次移动手牌位置（为了仿照内存中移动，我们把牌向后移动，也就是从后向前比较找插入位置），为新来的牌腾出一个位置，把新抓到的牌放入空位，一直到完成最后一张牌的插入，我们也就同时完成了手牌的排序。其中的关键词有之前有序、移动、插入。

接下来可以举个例子操作一下，假设我开了天眼，可以看到牌堆里所有的牌，那么确定了抓牌顺序之后，我也就知道我会抓到哪些牌了，他们分别是6, 2, 7, 3, 8, 9，下面来模拟一下这个牌堆中的牌到了我的手里时候怎么就有序了，还有一个情况就是我用右手摸牌，左手拿牌，但是左手比较小，只能放的下6张牌，这时候可以看看实际的抓牌流程了。

起初情况是左手没有牌，右手抓了一张6:
L=_, _, _, _, _, _，R=6
这时候没有什么犹豫的，直接放到左手第一个位置就好了：
L=6, _, _, _, _, _ ，R=_
然后又抓到一张2，移动左手的牌，拿2和左手有序的牌进行比较，这是左手就1张6，将其向后移动得到：
L=_, 6, _, _, _, _ ，R=2
接下来需要把右手的2放到左手腾出的位置即可：
L=2, 6, _, _, _, _ ，R=_
紧接着又抓到一张7，发现放到后面就可以，不用移动元素了：
L=2, 6, 7, _, _, _ ，R=_
然后又抓到一张3，其实找插入位置还有另一种形式，就是放到最后，然后不断的换到合适的位置，用这张3来试一下：
L=2, 6, 7, _, _, _ ，R=3
先放到左手最后：
L=2, 6, 7, 3, _, _ ，R=_
然后和前面比3大的换一下位置：
L=2, 6, 3, 7, _, _ ，R=_
再换一次找到了真正插入的位置：
L=2, 3, 6, 7, _, _ ，R=_
后面的8，9两张都不需要交换位置，直接放到最后就得到了最终的结果：
L=2, 3, 6, 7, 8, 9 ，R=_

代码实现

/*
功能：  交换两个变量
参数：  element1--被交换的第一个元素的地址
        element2--被交换的第二个元素的地址
返回值：无
注意：  只用来表示思路，不考虑指针为空等特殊情况
*/
void swap_data(int* element1, int* element2)
{
    int middle_value = *element1;
    *element1 = *element2;
    *element2 = middle_value;
}

/*
功能：  插入排序，实现数组元素从小到大排列
参数：  array--表示待排序的数组，此处会退化成指针
        count--数组元素的个数
返回值：无
注意：  只用来表示思路，不考虑指针为空等特殊情况
*/
void insert_sort(int array[], int count)
{
    for (int pos = 1; pos < count; ++pos)
    {
        for (int insert_index = pos; insert_index > 0; --insert_index)
        {
            if (array[insert_index] < array[insert_index - 1])
                swap_data(&array[insert_index], &array[insert_index - 1]);
        }
    }
}