希尔排序算法分析及程序示例

实例说明

　　用希尔排序方法对数组进行排序。


实例解析

　　希尔排序 (Shell Sort) 是插入排序的一种。希尔排序基本思想是先取一个小于 n 的整数 d1 作为第一个增量，把文件的全部记录分成 d1 个组。所有距离为 d1 的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量 d2<d1 重复上述的分组和排序，直至所取的增量 dt=1(dt<dt-1<…<d2<d1), 即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。


Shell 排序的算法描述如下 :

void ShellPass(SeqList R,int d){ // 希尔排序中的一趟排序， d 为当前增量
　　for(i=d+1;i<=n;i++) 　　　　　// 将 R[d+1..n] 分别插入各组当前的有序区
　　　　if(R[i].key<R[i-d].key){
　　　　　　R[0]=R[i]; j=i-d; 　　//R[0] 只是暂存单元，不是哨兵
　　　　　　do{ 　　　　　　　　　// 查找 R[i] 的插入位置
　　　　　　　　R[j+d]=R[j]; 　　// 后移记录
　　　　　　　　j=j-d; 　　　　　// 查找前一记录
　　　　　　}while(j>0 && R[0].key < R[j].key);
　　　　　　R[j+d]=R[0]; 　　　　// 插入 R[i] 到正确的位置上
　　　　} //endif
}//ShellPass

void ShellSort(SeqList R){
　　int increment=n; 　　　　　　　// 增量初值，设 n>0
　　do{
　　　　increment=increment/3+1;　// 求下一增量
　　　　ShellPass(R,increment);　 // 一趟增量为 increment 的 Shell 插入排序
　　}while(increment>1);
}//ShellSort

　　注意：当增量 d=1 时，希尔排序和插入排序基本一致，只是由于没有哨兵而在内循环中增加了一个循环判定条件“ j> 0 ”，以防下标越界。


程序代码—希尔排序

#include <stdio.h>
#define MAX 255
int R[MAX];

void ShellPass(int d,int n){ /* 希尔排序中的一趟排序， d 为当前增量 */
   int i,j;
   for(i=d+1;i<=n;i++) /* 将 R[d+1..n] 分别插入各组当前的有序区 */
      if(R[i]<R[i-d]){
         R[0]=R[i]; j=i-d; /*R[0] 只是暂存单元，不是哨兵 */
         do{ /* 查找 R[i] 的插入位置 */
            R[j+d]=R[j]; /* 后移记录 */
            j=j-d; /* 查找前一记录 */
         }while(j>0 && R[0]<R[j]);
         R[j+d]=R[0]; /* 插入 R[i] 到正确的位置上 */
      }/*endif*/
}/*end of ShellPass*/

void Shell_Sort(int n){
   int increment=n; /* 增量初值，设 n>0*/
   do{
      increment=increment/3+1; /* 求下一增量 */
      ShellPass(increment,n); /* 一趟增量为 increment 的 Shell 插入排序 */
   }while(increment>1);
}/*ShellSort*/

void main(){
   int i,n;
   clrscr();
   puts("Please input total element number of the sequence:");
   scanf("%d",&n);
   if(n<=0 || n>MAX){
      printf("n must more than 0 and less than %d.\n",MAX);
      exit(0);
   }
   puts("Please input the elements one by one:");
   for(i=1;i<=n;i++)
      scanf("%d",&R[i]);
   puts("The sequence you input is:");
   for(i=1;i<=n;i++)
      printf("%4d",R[i]);
   Shell_Sort(n);
   puts("\n The sequence after shell_sort is:");
   for(i=1;i<=n;i++)
      printf("%4d",R[i]);
   puts("\n Press any key to quit…");
   getch();
}


归纳注释

　　增量序列的选择：希尔排序的执行时间依赖于增量序列。好的增量序列的共同特征： ① 最后一个增量必须为 1; ② 尽量避免序列中的值 ( 尤其是相邻的值 ) 互为倍数的情况。有人通过大量的实验，给出了目前较好的结果：当 n 较大时，比较和移动的次数约在 n^( 1.25)～1.6n^( 1.25) 之间。

　　希尔排序的时间性能优于直接插入排序，因为： ① 当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。 ② 当 n 值较小时， n 和 n^2 的差别也较小，即直接插入排序的最好时间复杂度 O(n) 和最坏时间复杂度 O(n^2) 差别不大。 ③ 在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量 di 逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按 di-1 作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。因此，希尔排序在效率上较直接插入排序有较大的改进。

　　稳定性：希尔排序是不稳定的。因为两个相同关键字在排序前后的相对次序发生了变化。