直接插入排序和希尔排序--c语言

前言：

还在用冒泡排序吗？还在为冒泡排序的时间复杂度而苦恼吗？来这里，希尔排序告诉你冒泡排序有多逊，而它有多强！

冒泡排序：“你看不起谁啊？我可是万千初学者的最爱！我.....”。

好啦，我们先不管冒泡选手的吐槽，注意力重新放在我们希尔排序的身上。下面有请希尔排序做个自我介绍哈！

希尔排序：“嗯哼，介绍我之前先介绍插入排序老弟吧？这可是我的最忠实的小弟，我可少不了它的帮助。嗯，是这样的。”

额，既然如此，那我们就先来看看插入排序好了（冒泡排序叫嚣道：“呵~ 希尔排序好大的排场呀! ”）

直接插入排序：（升序讲解）

插入排序："大家好，我是插入排序！我实现的方式就是假设数组里前 i-1 个数都是有序的，在插入第 i 个元素时先把它临时保存起来，然后将它与前面的的数据逐一对比。开始时若第 i-1 个数比第 i 个数据大的话就放在 i 所在的位置，然后往前继续查找，直到找到比插入的元素小的数时，把最开始保存的数插到其后面，那么一个数据的插入就完成了！"

冒泡排序找到漏洞，赶紧插嘴道：“那你也是建立在前 i 个元素是有序的啊，这你怎么解决？”

插入排序气定神闲：“别急，我会慢慢讲的。一般让我们排序时，都是给好的一个无序的数组，我们可以假设最初只有一个数据，然后在原数组上取第二个数模拟上面讲到的规则进行插入，此时前两个数就是有序的了。然后插入第三个数，重复操作，直到把整个数组元素插入进去就会完成整个数组的排序了。”

直接插入排序图解：

直接插入排序代码：

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

直接插入排序时间复杂度：

如果运气差一点，刚好是倒序数组，那么时间复杂度就是O()了。（冒泡排序：“嘿嘿嘿...”）

但是如果是部分升序有序的数组，插入排序就非常nice了，比如 2 3 5 6 1 2 8 9。冒泡排序来了还得是 次比较操作，但是这里插入排序就会省事很多，读者有兴趣可以自己试试看。

插入排序的特性总结：

1. 元素集合越接近有序，直接插入排序算法的时间效率越高

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

3. 空间复杂度：O(1)，它是一种稳定的排序算法

4. 稳定性：稳定

冒泡：“切~”。

下面有请希尔排序登场！

希尔排序：（升序讲解）

希尔排序：“到我啦？好，好，首先我也讲一下我的实现原理哈！先选定一个整数gap，把待排序数组（n个元素）中所有元素分成个 n/gap 组，所有距离为gap的元素分在同一组内，并对每一组内的元素进行类似直接插入排序的排序（直接插入排序的gap是1）。然后缩小gap，重复上述分组和排序的工 作。当到达gap=1时，就进行直接插入排序。这样数组就排好啦！”

冒泡排序：“听着就好麻烦！就你？就你？”

希尔排序：“我们笔下见真章！”

希尔排序图解：

希尔排序代码：

void ShellSort(int* a, int n) //n是数组的大小
{
    int gap = n;
    while (gap > 1)
    {
        //这里的gap大于1时，其实是相当于进行了预排序，跨度较大，每次都把每组较大的数
          轻轻松松地放在 了靠后的位置，最后一步步的缩小跨度，从而实现排序的思想。
        gap = gap / 3 + 1;
        for (int i = 0; i < n - gap; ++i)
        {
            //下面的代码就是类似直接插入排序的思想，只不过跨度变为gap而已了。
            int end = i;
            int tmp = a[end + gap];
            while (end >= 0)
            {
                if (a[end] > tmp)
                {
                    a[end + gap] = a[end];
                    end -= gap;
                }
                else
                {
                    break;
                }
            }
            a[end + gap] = tmp;
        }

    }
}

希尔排序时间复杂度：

希尔排序：“所以我厉害在哪里呢？嗯哼~？”

冒泡排序：“喂，能不能不要一副 “老子多牛的样子” ？”

回归正题：

这里的时间复杂度其实是不太好用正常的数学方式来解决的，通过前人的计算分析，以上面的代码为例，时间复杂度大概在O(N^1.25)到O(1.6*N^1.25)之间。

稳定性：不稳定

总结：

希尔排序：“咳咳~，插入，咱们走吧，不和冒泡玩，它太逊了，和它在一起丢人。”

插入排序：“嗯嗯！不和冒泡玩！^_^”。

冒泡排序：“你们两个......，能不能不要人身攻击啊！”。

希尔排序：“逊👎”。

插入排序：“嗯嗯！👎！”。

冒泡排序：“啊！我走，行了吧！呜呜呜~”。