【排序算法】——插入排序

前言

简介

基本思想

1.直接插入排序

2.希尔排序

代码实现

1.直接插入排序

2.希尔排序

总结

1.时空复杂度

2.稳定性

尾声

前言

排序(Sorting) 是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个关键字有序的序列。所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

排序算法，就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视，尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。

简介

所谓排序算法，即通过特定的算法因式将一组或多组数据按照既定模式进行重新排序。这种新序列遵循着一定的规则，体现出一定的规律，因此，经处理后的数据便于筛选和计算，大大提高了计算效率。对于一个排序算法的优劣，我们需要从它的时间复杂度、空间复杂度和稳定性三个方面来考虑。什么叫稳定性呢？即当两个相同的元素同时出现于某个序列之中，则经过一定的排序算法之后，两者在排序前后的相对位置不发生变化。换言之，即便是两个完全相同的元素，它们在排序过程中也是各有区别的。

本篇文章讲述的是排序算法中的插入排序，其中包含了两种排序算法，分别是直接插入排序和希尔排序，下面将会一一为大家详细介绍。（用升序进行讲解）

插入排序算法是基于某序列已经有序排列的情况下，通过一次插入一个元素的方式按照原有排序方式增加元素。这种比较是从该有序序列的最末端开始执行，即要插入序列中的元素最先和有序序列中最大的元素比较，若其大于该最大元素，则可直接插入最大元素的后面即可，否则再向前一位比较查找直至找到应该插入的位置为止。

基本思想

插入排序的基本思想是，每次将1个待排序的记录按其关键字大小插入到前面已经排好序的序列中，寻找最适当的位置，直至全部记录插入完毕。

1.直接插入排序

下面我们首先来看一看直接插入算法的动图演示：

看了上图之后，我们可以得知，直接插入排序是在一个给定的数组中，我们从第二个元素开始，与之前的元素一一进行比较：

· 若是该位置的元素小于前一个元素，那么就将该位置元素与更前一位的元素再次进行比较，直到前面没有元素，那么此时该元素就放在数组的首位。

· 若是该位置的元素大于或者等于前一个元素，那么就把该位置的元素放到前一个元素的后面（具体的方式在下面的代码实现中进行讲解）。

这就是直接插入排序的具体思路，有了它我们便可以写出我们的直接插入排序算法。

2.希尔排序

当数组中的元素越接近有序时，直接插入排序算法的时间效率越高；但是当数组中的元素越不接近有序，特别是倒序时，此时要使元素正序排列，使用直接插入算法的时间效率就非常低了，那我们能不能对直接插入算法进行一些优化呢?

答案是可以的。既然我们说当元素越有序时的时间效率越高，那我们可以把元素先分为若干份，先将这些部分使用直接插入算法变得有序后再去整体进行直接插入排序算法，从而达到目的，这就是希尔排序。

希尔排序法又称缩小增量法。希尔排序算法的基本思想是：先选定一个整数，记为num，用num计算出一个距离gap = n / num + 1，n为元素总数，把待排序元素分成各组，所有的距离相等的记录分在同一组内，并对每⼀组内的元素进行排序，然后gap = gap / num + 1得到下⼀个距离，再将数组分成各组，进行直接插入排序，当gap == 1时，就相当于直接插入排序。举个例子，此时我们的num取2，先看下面图片

上图中n = 10，我们选取一个整数2计算得到第一个距离gap = 10 / 2 + 1 = 5，此时第一个元素9和与他距离为5的第六个元素4为一组，6 + 5 = 11，由于数组中只有十个元素，因此第一组中只有两个元素，9和4，后面以此类推。将这些组分别进行直接插入排序后我们更新gap = gap / 2 + 1 = 2，此时相距为2的元素为一组，再次对每一组进行直接插入排序，直到gap == 1，此时再进行直接插入排序，这样，我们就完成了希尔排序算法。当 gap > 1 时都是预排序，目的是让数组更接近于有序。当 gap == 1 时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。其中整数num的取值有各种各样，不过一般来说，我们的num = 3。

代码实现

1.直接插入排序

先看代码

void Insert_sort(vector<int>& a)
{
    //从第二个元素开始进行排序，一直到最后一个元素
    for (int i = 1; i < a.size(); i++)
    {
        //用end记录需要排序的元素的前一个元素的下标，tmp用来保存当前需要排序的元素
        int end = i - 1, tmp = a[i];
        //用while循环对a[i]进行排序
        while (end >= 0)
        {
            //end位置的元素大于tmp(也就是a[i])时，把end位置的元素复制到end + 1的位置上，并且end--，继续进行比较
            if (a[end] > tmp)
            {
                a[end + 1] = a[end];
                end--;
            }
            //因为我们插入一个新的元素时，它前面的元素都已经是有序的，因此当end位置的元素不大于tmp时，循环结束
            else break;
        }
        //当循环结束时由于end进行一次减一操作，所以该元素所处的正确位置为end + 1
        a[end + 1] = tmp;
    }
}

解析：通过注释相信大家基本上已经能够了解代码的意思，接下来我会通过画图的方式再给大家进行更加详细的介绍

通过上面的图相信大家对直接插入排序已经十分了解了。

2.希尔排序

在前面已经为大家详细的介绍希尔排序的过程，下面的代码大家可以参考一下：

void Shell_sort(vector<int>& a)
{
    //先将元素个数赋值给gap，这样在循环中可以很好的控制gap
    int gap = a.size();
    while (gap > 1)
    {
        gap = gap / 3 + 1;
        //我们可以不必一组一组的进行排序，而是i走到哪一组就对哪一组的元素进行排序，这样可以节省一层for循环
        for (int i = gap; i < a.size(); i++)
        {
            //因为此时的每一组的元素相距为gap，因此我们从gap位置开始枚举，即每一组的第二个元素
            //此时要找到前一个元素的下标end需要用i - gap
            int end = i - gap, tmp = a[i];
            while (end >= 0)
            {
                if (a[end] > tmp)
                {
                    //与上面同理，我们每组中元素相距gap，因此end + gap才是end位置后的那一个元素位置
                    a[end + gap] = a[end];
                    end-=gap;
                }
                else break;
            }
            //与上面同理
            a[end + gap] = tmp;
        }
    }
}

注：上述两种排序的算法博主用的是从第二个元素去找前一个元素，大家也可以反过来，例如在直接插入排序算法中for循环改为 for(int i = 0; i < a.size() - 1; i++) 此时 end = i，tmp = a[i + 1]。根据个人习惯选择即可。

总结

1.时空复杂度

简单分析我们可以得到直接插入排序算法的时间复杂度和空间复杂度

直接插入排序：

时间复杂度：O(N ^ 2)

空间复杂度：O(1)

对于希尔排序来说，对于整数num的取值不同，其时间复杂度也不同，导致很难去计算时间复杂度，因此很多书中给出的希尔排序的时间复杂度都不固定。《数据结构(C语言版)》--- 严蔚敏书中给出的时间复杂度为：

希尔排序：

时间复杂度：O(nlogn ~ n ^ 2)

空间复杂度：O(1)

希尔排序算法是在直接插入排序算法的基础上进行改进而来的，综合来说它的效率肯定是要高于直接插入排序算法的。

2.稳定性

在排序算法中，我们不光要关注算法的时空复杂度，还在看看算法的稳定性，什么是稳定性呢？

稳定性是假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

执行过程中，若遇到和插入元素相等的位置，则将要插人的元素放在该相等元素的后面，因此插入该元素后并未改变原序列的前后顺序。我们认为插入排序是一种稳定的排序方法。但是对于希尔排序来说，因为对数据进行了分组，因此在排序过程中会出现相同的元素不在同一组中，导致其相对位置发生了改变，因此我们说希尔排序是不稳定的。