你真的懂排序算法吗？带你理解数论中排序本质，为什么希尔排序效率竟然如此之高？_排序的本质

关于排序，我们从冒泡讲起：

首先，我们写一个最简单的插入排序，这个是最最基础，也是所有人看到排序问题最直接的想法

//直接插入排序函数
void InsertSort(int a[], int n)
{
    for(int i= 1; i<n; i++){
        if(a[i] < a[i-1]){//若第 i 个元素大于 i-1 元素则直接插入；反之，需要找到适当的插入位置后在插入。
            int j= i-1;
            int x = a[i];
            while(j>-1 && x < a[j]){  //采用顺序查找方式找到插入的位置，在查找的同时，将数组中的元素进行后移操作，给插入元素腾出空间
                a[j+1] = a[j];
                j--;
            }
            a[j+1] = x;      //插入到正确位置
        }
        print(a,n,i);//打印每次排序后的结果
    }
}

我们看到，插入排序由于内外有两层循环，时间复杂度为o(n^2)；

但是我们再来看一下希尔排序（希尔排序原理请自行查找）

#include <stdio.h>
int shsort(int s[], int n)    /* 自定义函数 shsort()*/
{
    int i,j,gap;
    gap=n/2;    /*确定固定增虽值*/
    while(gap>=1)
    {
        for(i=gap+1;i<=n;i++)    /*数组下标从d+1开始进行直接插入排序*/
        {
            s[0]=s[i];    /*设置监视哨*/
            j=i-gap;    /*确定要进行比较的元素的最右边位置*/
            while((j>0)&&(s[0]<s[j]))
            {
                s[j+d]=s[j];    /*数据右移*/
                j=j-gap;    /*向左移d个位置V*/
            }
            s[j + gap]=s[0];    /*在确定的位罝插入s[i]*/
        }
        gap = gap/2;    /*增里变为原来的一半*/
    }
return 0;
}

可以清晰地看出，希尔排序的内部就是分组进行插入排序，那么为什么希尔排序会比插入排序快如此多呢？

首先我们看下排序的本质：

为啥希尔能突破O(N^2)的界，可以用逆序数来理解，假设我们要从小到大排序，一个数组中取两个元素如果前面比后面大，则为一个逆序，容易看出排序的本质就是消除逆序数，可以证明对于随机数组，逆序数是O(N^2)的，而如果采用“交换相邻元素”的办法来消除逆序，每次正好只消除一个，因此必须执行O(N^2)的交换次数，这就是为啥冒泡、插入等算法只能到平方级别的原因，反过来，基于交换元素的排序要想突破这个下界，必须执行一些比较，交换相隔比较远的元素，使得一次交换能消除一个以上的逆序，希尔、快排、堆排等等算法都是交换比较远的元素，只不过规则各不同罢了。

 

那么会有人问了：不相邻的交换可以一次消除多个逆序对，那么会不会造成更多的逆序对呢？

答案是：这个需要人为制造规则保证这件事不发生，举个例子：

假设从小到大排序，简单起见设数组元素两两不等

现在发现了a[i]>a[j]，i<j，考虑下标闭区间[i,j]这个范围的j-i+1个元素，对任意i<k<j，考虑a[k]

若a[k]<a[j]，交换a[i]和a[j]后，三者的逆序数从2变为1（例如3 1 2变成2 1 3）

若a[k]>a[i]，交换a[j]和a[i]后，三者的逆序数从2变为1（例如2 3 1变成1 3 2）

若a[i]>a[k]>a[j]，交换a[i]和a[j]后，三者的逆序数从3变为0（例如3 2 1变成1 2 3）

当然，上面每条都重复计算了a[i]和a[j]的逆序关系，但是减掉重复计算的数量，每次交换，逆序数也必然是递减的，除非你去交换两个本来就有序的元素

 

至此，相信你对排序的本质有了新的认识。