那些年我们排过的序之希尔排序

零四 一三 二七 三八 四九 四九 五五 六五 七六 九七

1&＃xff0e;增量序列的选择

Shell排序的执行时间依赖于增量序列。

好的增量序列的共同特征&＃xff1a;

① 最后一个增量必须为1&＃xff1b;

② 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。

有人通过大量的实验&＃xff0c;给出了较好的结果&＃xff1a;当n较大时&＃xff0c;比较和移动的次数约在nl.25到1.6n1.25之间。

2&＃xff0e;Shell排序的时间性能优于直接插入排序

希尔排序的时间性能优于直接插入排序的原因&＃xff1a;

①当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。

②当n值较小时&＃xff0c;n和n2的差别也较小&＃xff0c;即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n2)差别不大。

③在希尔排序开始时增量较大&＃xff0c;分组较多&＃xff0c;每组的记录数目少&＃xff0c;故各组内直接插入较快&＃xff0c;后来增量di逐渐缩小&＃xff0c;分组数逐渐减少&＃xff0c;而各组的记录数目逐渐增多&＃xff0c;但由于已经按di-1作为距离排过序&＃xff0c;使文件较接近于有序状态&＃xff0c;所以新的一趟排序过程也较快。

因此&＃xff0c;希尔排序在效率上较直接插入排序有较大的改进。

希尔排序是按照不同步长对元素进行插入排序&＃xff0c;当刚开始元素很无序的时候&＃xff0c;步长最大&＃xff0c;所以插入排序的元素个数很少&＃xff0c;速度很快&＃xff1b;当元素基本有序了&＃xff0c;步长很小&＃xff0c;插入排序对于有序的序列效率很高。所以&＃xff0c;希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序&＃xff0c;我们知道一次插入排序是稳定的&＃xff0c;不会改变相同元素的相对顺序&＃xff0c;但在不同的插入排序过程中&＃xff0c;相同的元素可能在各自的插入排序中移动&＃xff0c;最后其稳定性就会被打乱&＃xff0c;所以shell排序是不稳定的。

举例阐述&＃xff1a;

例如&＃xff0c;假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]&＃xff0c;如果我们以步长为5开始进行排序&＃xff0c;我们可以通过将这列表放在有5列的表中来更好地描述算法&＃xff0c;这样他们就应该看起来是这样&＃xff1a;

13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

然后我们对每列进行排序&＃xff1a;

10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

将上述四行数字&＃xff0c;依序接在一起时我们得到&＃xff1a;[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].这时10已经移至正确位置了&＃xff0c;然后再以3为步长进行排序&＃xff1a;

10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45

排序之后变为&＃xff1a;

10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94

最后以1步长进行排序&＃xff08;此时就是简单的插入排序了&＃xff09;。

图示&＃xff1a;

C&＃43;&＃43;代码实现&＃xff1a;

#include
 
void  shellsort(int *data, size_t size);

 int i, j, temp;
 int gap &＃61; 0;

int main()
{
     const int n &＃61; 5;

     int a[] &＃61; {5, 4, 3, 2, 1};
  shellsort(a,5);
   /*  while (gap<&＃61;n)
     {
          gap &＃61; gap * 3 &＃43; 1;
     }
     while (gap > 0)
     {
         for ( i &＃61; gap; i          {
             j &＃61; i - gap;
             temp &＃61; a[i];            
             while (( j >&＃61; 0 ) && ( a[j] > temp ))
             {
                 a[j &＃43; gap] &＃61; a[j];
                 j &＃61; j - gap;
             }
             a[j &＃43; gap] &＃61; temp;
         }
         gap &＃61; ( gap - 1 ) / 3;
     } */
  for(i&＃61;0;i<5;i&＃43;&＃43;)
     printf("%d\n",a[i]);
 }

void shellsort(int *data, size_t size)
{

 int key;
  int j &＃61; 0;
     for (gap &＃61; size / 2; gap > 0; gap /&＃61; 2)
         for ( i &＃61; gap; i          {
 
              key &＃61; data[i];
            
              for( j &＃61; i -gap; j >&＃61; 0 && data[j] > key; j -&＃61;gap)
              {
                 data[j&＃43;gap] &＃61; data[j];
               } 
              data[j&＃43;gap] &＃61; key;
          }
 }