数据结构基础希尔排序之算法复杂度浅析

刺骨的言语ヽ痛彻心扉 2022-08-04 15:55 116阅读 0赞

希尔排序（Shell Sort）又叫做缩小增量排序（diminishing increment sort），是一种很优秀的排序法，算法本身不难理解，也很容易实现，而且它的速度很快。

Shell排序通过将数据分成不同的组，先对每一组进行排序，然后再对所有的元素进行一次插入排序，以减少数据交换和移动的次数。

**希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。**

由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以，**Shell排序是不稳定的。**

[插入排序（Insertion Sort）][Insertion Sort]的一个重要的特点是，如果原始数据的大部分元素已经排序，那么插入排序的速度很快（因为需要移动的元素很少）。从这个事实我们可以想到，如果原始数据只有很少元素，那么排序的速度也很快。－－希尔排序就是基于这两点对插入排序作出了改进。

例如，有100个整数需要排序。

1.  第一趟排序先把它分成50组，每组2个整数，分别排序。
2.  第二趟排序再把经过第一趟排序后的100个整数分成25组，每组4个整数，分别排序。
3.  第三趟排序再把前一次排序后的数分成12组，第组8个整数，分别排序。
4.  照这样子分下去，最后一趟分成100组，每组一个整数，这就相当于一次插入排序。

由于开始时每组只有很少整数，所以排序很快。之后每组含有的整数越来越多，但是由于这些数也越来越有序，所以排序速度也很快。

希尔排序平均效率是O(nlogn)。其中分组的合理性会对算法产生重要的影响。现在多用D.E.Knuth的分组方法。下面来分析原始的希尔排序的时间复杂度，初始步长d=n/2，下一次步长d=d/2

> 第一次比较次数，每组2个元素：1\*n/2
> 
> 第二次比较次数，每组4个元素：最坏(1+2+3)\*n/4
> 
> 第三次比较次数，每组8个元素：最坏(1+2+3+……+7)\*n/8

... ...

2^(m-1) ( m 表示第几次比较 ) < 每组最坏的元素比较次数 < 2^(m)

例子 ：2^2 < 7 < 2^3 （第 3 次比较，最后一个元素的最差比较次数 ）

**累加求极限，得到算法复杂度小于 O(n^2) 。**

**详见：http://blog.csdn.net/ginnosx/article/details/12263619**  
Shell排序比冒泡排序快5倍，比插入排序大致快2倍。Shell排序比起QuickSort，MergeSort，HeapSort慢很多。但是它相对比较简单，它适合于数据量在5000以下并且速度并不是特别重要的场合。它对于数据量较小的数列重复排序是非常好的。

由于开始时每组只有很少整数，所以排序很快。之后每组含有的整数越来越多，但是由于这些数也越来越有序，所以排序速度也很快。

然而，情况并不总是这么理想的，在一些特定（但并不算罕见）的情况下，虽然经过了很多趟排序但是数据却没有变得更有序。例如，如果用上面的算法对下面这些数进行排序

1, 9, 2, 10, 3, 11, 4, 12, 5, 13, 6, 14, 7, 15, 8, 16

会得到以下结果：

after gap(8): 1, 9, 2, 10, 3, 11, 4, 12, 5, 13, 6, 14, 7, 15, 8, 16
    after gap(4): 1, 9, 2, 10, 3, 11, 4, 12, 5, 13, 6, 14, 7, 15, 8, 16
    after gap(2): 1, 9, 2, 10, 3, 11, 4, 12, 5, 13, 6, 14, 7, 15, 8, 16
    after gap(1): 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16

在 gap=1 之前的每一趟排序都在浪费时间！

这种坏情形是可以避免的，就是把上面的增量数列（1, 2, 4, 8）改成Hibbard增量（1, 3, 5, 7）。

由此可见，增量数列的选择对希尔排序的性能有着极大的影响。\[Mark Allen Weiss\]指出，最好的增量序列是 Sedgewick提出的 (1, 5, 19, 41, 109,...)，该序列的项来自 9 \* 4^i - 9 \* 2^i + 1 和 4^i - 3 \* 2^i + 1 这两个算式。

下面是一个使用 Sedgewick增量 的希尔排序的完整C语言程序：

/*  使用 Sedgewick增量 的 Shell Sort 程序 */
    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    #define MAX 1000000	//这里设定要对多少个元素排序
    void shellsort(int A[], int N, int *);
    void printarray(int A[]);
    int main()
    {
      int i, s[MAX];
      int *sed;
      int sedgewick[] = {		// Sedgewick增量
        1073643521, 603906049, 268386305, 150958081, 67084289,
        37730305, 16764929, 9427969, 4188161, 2354689,
        1045505, 587521, 260609, 146305, 64769,
        36289, 16001, 8929, 3905, 2161,
        929, 505, 209, 109, 41,
        19, 5, 1, 0 };		//用 0 标记终点
      for (sed = sedgewick; *sed > MAX; sed++)	// 增量必须小于元素个数
        /* void */;
      for (i = 0; i < MAX; i++)
        s[i] = 1+(int) ((float)MAX*rand()/(RAND_MAX+1.0));
      printf("before   :");
      printarray(s);
      shellsort(s, MAX, sed);
      printf("after    :");
      printarray(s);
      return 0;
    }
    /* Shell Sort: 把增量序列放在数组里 */
    void shellsort(int v[], int n, int *sed)
    {
      int i, j, temp;
      int *gap;
      for (gap = sed; *gap > 0; gap++)
        for (i = *gap; i < n; i++)
          for (j = i - *gap; j>=0 && v[j]>v[j + *gap]; j -= *gap) {
    	temp = v[j];
    	v[j] = v[j + *gap];
    	v[j + *gap] = temp;
          }
    }
    void printarray(int a[])
    {
      int i;
      for (i = 0; i < MAX; i++)
        printf(" %d", a[i]);
      printf("/n");
    }
    
    // Sedgewick增量可用像下面那样的程序求得。
    /* 计算 Sedgewick增量 的程序 */
    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    #define wick  100
    void insertsort(int A[], int N);
    void printarray(int A[], int from, int to);
    int main()
    {
      int i, j;
      int sedge[wick];
      i = -1;
      do {
        ++i;
        sedge[i] = 9 * pow(4,i) - 9 * pow(2,i) + 1;
        printf("sedge[%d] = %d/n", i, sedge[i]);
      } while (sedge[i] > 0);
      printf("/n");
      j = 1;
      do {
        ++j;	// j = 0 和 j = 1 时该算式的解小于0，所以从 j = 2 开始取值。
        sedge[j+i-2] = pow(4,j) - 3 * pow(2, j) + 1;
        printf("sedge[%d] = %d/n", j+i-2, sedge[j+i-2]);
      } while (sedge[j+i-2] > 0);
      printf("/n");
      printarray(sedge, 0, j+i-2);
      insertsort(sedge, j+i-2);
      printarray(sedge, 0, j+i-2);
      return 0;
    }
    void printarray(int a[], int from, int to)
    {
      int i;
      for (i = from; i < to; i++)
        printf("%d, ", a[i]);
      printf("/n/n");
    }
    /* 从大到小排序 */
    void insertsort(int A[], int n)
    {
      int  i, j, key;
      for (j = 1; j < n; j++)
        {
          key = A[j];
          i = j - 1;
          while (i >= 0 && A[i] < key)
    	{
    	  A[i+1] = A[i];
    	  --i;
    	}
          A[i+1] = key;
        }
    }

[Insertion Sort]: http://blog.csdn.net/liujiejesse/article/details/insertionsort.xml