vlambda博客
学习文章列表

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

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

//直接插入排序函数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]的逆序关系，但是减掉重复计算的数量，每次交换，逆序数也必然是递减的，除非你去交换两个本来就有序的元素

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