爱喝兽奶帝天荒

这个屌丝很懒，什么也没留下！

热门标签

数据结构——排序（1）：插入排序

作者：爱喝兽奶帝天荒 | 2024-08-08 07:18:52

踩

数据结构——排序（1）：插入排序

一、排序的概念

排序就是使一串记录按照其中的某个或某些关键字的大小，递增或递减排列起来的操作。

二、排列的运用

（1）购物筛选排序

（2）院校排名排序

三、常见的排序算法

四、插入排序

插入排序的基本思想是将待排序的记录按其关键码值的大小逐个插入到一个已经排好序的一个有序序列列中，直到所有记录插入完为止，得到一个新的有序序列。

联想我们在实际中玩的扑克牌，就用到了插入排序的思想~

1.直接插入排序

（1）思路

插入到第i个元素时，其前面的元素已经排好序了，此时将第i个元素的大小与第i-1、i-2……个元素的大小进行比较，找到合适的位置，将原来位置上的元素后移，并将第i个元素插入。

（2）过程图示

我们以数组{2，1，3，5，4，8}为例：

①首先end指的是已排好序的最后一个元素；tmp为end之后的元素，即要比较插入的元素。

如图：tmp比end小，那么应该将tmp往前遍历。让end+1位置的数据为end位置的数据，end往前遍历，此时end<0无法再遍历，则跳出循环。

②③继续遍历：随后的两次中tmp均大于end对应的数据，直接进行下一此遍历。

④此时tmp小于end对应的位置，令end+1位置的数据为end位置的数据，end后移继续遍历。此时tmp大于end对应位置的数据，那么令此时end+1位置的数据为tmp。

⑤继续遍历，此时tmp大于end，直接进行下一次遍历。

⑥继续遍历我们发现end指向最后一个数据时，tmp越界了，说明该情况不合理。我们也可以知道在写代码时，end的约束条件应该是<n-1。

至此遍历完成，所有数据也排为了升序。

（3）代码实现


void InsertSort(int* arr, int n)
{
    for(int i = 0 ; i < n - 1; i ++)
    {    
        int end = i;
        int tmp = arr[end + 1];
        while(end >= 0)
        {
            if(tmp < arr[end])
            {
                arr[end+1] = arr[end];
                end--;
            }
            else 
            {    
                break;
            }
        }
        arr[end+1] = tmp;
    }
}

(4)代码解释

①首先最外层的for循环，用i遍历下标为0 ~ n-2的数据，即最后一个数据没有被遍历（前面有解释，end = i ，且end不能为最后一个数据，因为tmp会越界）；

②end为已经排好序的范围的最后一个数据；tmp为被比较之后插入的元素；

③while循环用来限制end不能出界，即end<0或者tmp>=arr[end]（else情况），都会跳出循环执行下一步：令end+1位置的数据为tmp储存的数据；

④如果tmp比end指向的数据小，即tmp应该排在end前面，就令end+1的位置数据为end对应的数据，相当于给tmp腾位置，遍历寻找一个end<tmp且end+1>tmp的位置，插入tmp。

（5）特性

①元素集合越接近有序，算法的时间效率越高；

②时间复杂度：O(n^2):最差的情况是序列为降序（要排列为升序），即Tmp要与其前面的每个数据都比较。O(2+3+……+n-1+n) = O(n^2);

③空间复杂度：O(1)。

2.希尔排序

我们学习了直接插入排序，但是它的时间复杂度为O(n^2)，效果并不是很理想。而这个结果是基于降序的情况计算的，那么可以思考一下，我们是不是能够将其优化一下，避免这种的情况出现呢？

（1）思路

希尔排序法又称缩小增量法。

先选定一个整数（定义为gap），把待排序的文件分成若干组，所有的距离相等的数据分在同一组，并对每一组的数据进行排序，然后gap = gap / 3 + 1得到下一个新的gap，再将数据进行分组并对每组进行插入排序，在这个过程中gap会越来越小，当gap等于1时就相当于直接插入排序算法。（那么，为什么新的gap要等于gap/3+1呢？这是因为相较于除以2、除以4来说，除以3所分的组数不是太多，也不会太少；并且在最后+1避免了达不到gap=1的情况。）

（2）过程图示

我们以数组{9，1，2，5，7，4，8，6，3，5}、gap等于5为例：

相同颜色的数据为一组，由于gap等于5，我们将以上10个数据分为了5组，每组2个数据。将每组的两个数据进行比较（此时靠前的数据为end，靠后的数据为tmp），如果tmp小于end对应的数据，则让end+gap对应的数据为end所对应的数据，end往前遍历（end-gap）。巧的是，在这几组中end-gap均小于0，跳出循环。然后继续遍历…… 就这样，我们将每组数据进行了排序，得到{4，1，2，3，5，9，8，6，5，7}；

gap改变，gap等于2、1的情况亦是如此：

得到{2，1，4，3，5，6，5，7，8，9}；

得到{1，2，3，4，5，5，6，7，8，9}，至此排序完成。

（3）代码实现

我们可以根据将每组进行排序的思路写代码：


void ShellSort(int* arr, int n)
{
    int gap = 3;
    for(int i = 0 ; i < gap ; i ++)
    {
        for(int i = 0 ;i < n - gap; i += gap)
        {
            int end = i;
            int tmp = arr[end + gap];
            while(end >= 0)
            {    
                if(tmp < arr[end])
                {
                    arr[end + gap] = arr[end];
                    end -= gap;
                }
                else 
                {
                    break;
                }
            }
            arr[end + gap] = tmp;
        }
    }
}

第一个for循环是将分成的3组进行排序，第二个for循环及以下是将每组数据进行排序，只是在直接插入排序的基础上的优化。可是，现在怎么比之前还要多一个循环呢？可想而知时间复杂度并不理想，我们应该设法去掉这个for循环：


void ShellSort(int* arr, int n)
{
    int gap = n;
    while(gap > 1)
    {
        gap = gap / 3 + 1;
        for(int i = 0 ; i < n - gap ; i ++)
        {
            int end = i;
            int tmp = arr[end+gap];
            while(end >= 0)
            {
                if(tmp < arr[end])
                {    
                    arr[end + gap] = arr[end];
                    end -= gap;
                }
                else
                {
                    break;
                }
            }
            arr[end + gap] = tmp;
        }    
    }
}

区别在于前者是每一组内部的数据先进行比较（以组为单位），后者为按照原有的顺序进行遍历，当然所插入的数据是与其所在组中的数据进行比较。

(4)代码解释

其实与直接插入排列类似：

①gap的限制条件为gap>1，gap不能等于1（如果等于1，gap=gap/3+1的计算中gap一直为1，会造成死循环）；

②最外层的for循环，用i遍历下标为0 ~ n-gap-1的数据，即end-gap位置的数据没有被遍历。解释同上，end = i ，且end不能为最后一个数据，因为tmp会越界（若end=n-gap，那么tmp=n-gap+gap=n，此时越界）；

③end为已经排好序的范围的最后一个数据；tmp为被比较之后插入的元素；

④while循环用来限制end不能出界，即end<0或者tmp>=arr[end]（else情况），都会跳出循环执行下一步：令end+gap位置的数据为tmp储存的数据；

⑤如果tmp比end指向的数据小，即tmp应该排在end前面，就令end+gap的位置数据为end对应的数据，相当于给tmp腾位置，遍历寻找一个end<tmp且end+gap>tmp的位置，插入tmp。

（5）特性

①希尔排序是对直接插入排序的优化；

②gap>1都是预排序，目的是让数组更接近有序；当gap等于1时，数组已经接近有序，这样排序的效率更高。

（6）时间复杂度

外层循环的时间复杂度为O(log2 N)或者O(log3 N)，即为O(log N)；

内存循环的时间复杂度为O(n^1.3)：

假设有n个数据，距离为gap，那么一共有gap组，每组有n/gap个数据。

最坏的情况下：

每组的移动次数为1+2+3+……+（n/gap - 1），一共有gap组，因此总移动总数为gap*[ 1+2+3+……+（n/gap - 1）]。

当gap为n/3时，移动总次数为：n/3 *(1 +2 ) = n；

当gap为n/9时，移动总次数为：n/9 *(1 +2 + …… + 8) = n/9 * 8（1+8）/2 = 4n；

最后一趟，gap等于1时，即为直接插入排序，内层循环排序消耗为n。

根据上述分析，可画出这样的曲线图：

因此，希尔排序在最初和最后的排序的次数都为n，即前一阶段排序次数是逐渐上升的状态，当到达某⼀顶点时，排序次数逐渐下降至n，而该顶点的计算暂时无法给出具体的计算过程。

希尔排序时间复杂度不好计算，因为 gap 的取值很多，导致很难去计算，因此很多书中给出的希尔排序的时间复杂度都不固定。

《数据结构(C语言版)》---严蔚敏书中给出的时间复杂度为：

五、写在最后

这节课我们学习了插入排序，而排序好几种。

敬请期待“选择排序”~

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/爱喝兽奶帝天荒/article/detail/946789