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

  • Post author:
  • Post category:其他




前言

上次聊到了

快速排序

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

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



插入排序

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

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

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

  1. 起初情况是左手没有牌,右手抓了一张6:

    L=

    _, _, _, _, _, _

    ,R=

    6

  2. 这时候没有什么犹豫的,直接放到左手第一个位置就好了:

    L=

    6, _, _, _, _, _

    ,R=

    _

  3. 然后又抓到一张2,移动左手的牌,拿2和左手有序的牌进行比较,这是左手就1张6,将其向后移动得到:

    L=

    _, 6, _, _, _, _

    ,R=

    2

  4. 接下来需要把右手的2放到左手腾出的位置即可:

    L=

    2, 6, _, _, _, _

    ,R=

    _

  5. 紧接着又抓到一张7,发现放到后面就可以,不用移动元素了:

    L=

    2, 6, 7, _, _, _

    ,R=

    _

  6. 然后又抓到一张3,其实找插入位置还有另一种形式,就是放到最后,然后不断的换到合适的位置,用这张3来试一下:

    L=

    2, 6, 7, _, _, _

    ,R=

    3

  7. 先放到左手最后:

    L=

    2, 6, 7, 3, _, _

    ,R=

    _

  8. 然后和前面比3大的换一下位置:

    L=

    2, 6, 3, 7, _, _

    ,R=

    _

  9. 再换一次找到了真正插入的位置:

    L=

    2, 3, 6, 7, _, _

    ,R=

    _

  10. 后面的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]);
        }
    }
}



代码分析

以上代码就是模拟的抓牌过程,新加入的牌放到手牌最后,然后不断的和前面的手牌交换位置,“插入”到有序的手牌序列中,最后得到整体有序,配合前面具体的例子,可以把具体的那些数字带入到这段代码中,头脑中或者在纸上“运行”一下,你就会了解插入排序的原理了。



运行测试


快速排序–源码

如果你想运行测试一下,可以复制或者下载源代码,在本机运行测试一下,当然也可以选择

在线C++编译器

,把源代码复制到网页中运行查看结果,建议不明白的可以在本地环境单步调试一下,这样有助于理解算法思路。



版权声明:本文为shihengzhen101原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。