希尔排序（二）

古城微笑少年丶 2022-05-24 03:46 30阅读 0赞

# 另一种写法 #

上一篇博文[希尔排序（一）][Link 1]中的代码是基于希尔排序的原理，“直译”过来的。还有一种更简单的写法：

void shellsort_2(int a[], int n)    
    {    
        int j, gap;
    
        for (gap = n / 2; gap > 0; gap /= 2)   
        {
    #ifdef PRINT_PROCEDURE
                printf("-------- gap = %d--------\n",gap);
                print_array(a, n,gap);
    #endif
            for (j = gap; j < n; j++)//从数组第 gap个元素开始 ，直到 n-1 
            {       
                if ( a[j - gap] > a[j] )//每个元素与自己组内的数据进行直接插入排序 
                {    
                    int temp = a[j];    
                    int k = j - gap;    
                    while (k >= 0 && a[k] > temp)   //&&优先级更低 
                    {    
                        a[k + gap] = a[k];   // a[k]向后移动 ，腾出一个空位
                        k -= gap; 
                    }// 考察空位前面的元素
    
                    a[k+gap] = temp; //插入
    #ifdef PRINT_PROCEDURE
                    printf("[%d] insert to [%d]\n", j, k+gap);
                    print_array(a, n,gap);
    #endif 
                }
            }
         }
    }

# 对希尔排序的改进 #

**希尔排序的运行时间依赖于增量序列的选择**。 举个例子，如果使用 Shell 建议的序列，假使上一个增量为 4，那么当前的增量就是 2。因为2是4的因子，所以对于上一轮已经比较过的元素，这一轮会重复比较，这就造成了时间的浪费。更好的增量序列选择是**增量序列中的任何2个元素都是互素的**。目前已有学者提出了一些更有效的增量序列，这里仅展示其中的2个。

# Hibbard （希巴德）序列 #

Hibbard（希巴德）序列：

1,3,7,...,2k−1  1 , 3 , 7 , . . . , 2 k − 1  （k  k  为大于 0 0 的自然数）

使用 Hibbard 增量的希尔排序，其最坏情形的运行时间为 Θ(n3/2)  Θ ( n 3 / 2 ) ；  
其平均情形的运行时间被认为是 O(n5/4)  O ( n 5 / 4 ) （基于模拟结果）。

# Sedgewick （塞奇威克）序列 #

已知的最好的增量序列是由 Sedgewick（塞奇威克） 提出的： 1,5,19,41,109,....  1 , 5 , 19 , 41 , 109 , . . . .  这个序列中的项交替地取自以下2个序列：

1,19,109,505,2161,...,9∗(4k−2k)\+1  1 , 19 , 109 , 505 , 2161 , . . . , 9 ∗ ( 4 k − 2 k ) + 1  (k=0,1,2,3,...)  ( k = 0 , 1 , 2 , 3 , . . . )

5,41,209,929,3905,...,2k\+2(2k\+2−3)\+1  5 , 41 , 209 , 929 , 3905 , . . . , 2 k + 2 ( 2 k + 2 − 3 ) + 1  (k=0,1,2,3,...)  ( k = 0 , 1 , 2 , 3 , . . . )

使用 Hibbard 增量的希尔排序平均运行时间猜测为O(n7/6)  O ( n 7 / 6 ) ，最坏情形为O(n4/3)  O ( n 4 / 3 ) 。

# 改进后的C语言代码 #

void shell_sort_improved(int A[], int N, int inc_seq[])
    {
        int inc = 0;    
        int max_inc_idx = 0;  
        int i,j,k,tmp;
    
        while (inc_seq[ max_inc_idx + 1 ] < N)    
            max_inc_idx++;  //找到最大的且小于N的那个增量 
    
        for (i = max_inc_idx; i >= 0; --i)
        {        
            inc = inc_seq[i];      
    #ifdef PRINT_PROCEDURE
                printf("-------- gap = %d--------\n",inc);
    #endif 
            for (j = inc; j < N; ++j) 
            {   
                if( A[j-inc] > A[j] )
                {
                    tmp = A[j];            
                    k = j - inc;          
                    while (k >= 0 && A[k] > tmp) 
                    {          
                        A[ k + inc ] = A[k];   // A[k]向后移动 inc个位置，腾出一个空位
                        k -= inc;     // 继续考察空位前面的元素 
                    }           
                    A[k + inc] = tmp;  // tmp 插入到k的后面 
    #ifdef PRINT_PROCEDURE
                    printf("[%d] insert to [%d]\n", j, k+inc);
    #endif 
                }
            } 
        }   
    }

最后一个参数是增量序列。

# 完整代码及测试 #

#include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    
    #define PRINT_GAP 10
    #define ARRAY_LEN 100
    
    void print_array(int a[],  int len, int gap) // 用于打印数组
    {
        for(int i=0; i<len; ++i)
        {
            printf("[%2d]:%2d ", i, a[i]);
            if((i + 1) % gap == 0)
                printf("\n");
        }
        printf("\n\n");
    }
    
    void shell_sort_improved(int A[], int N, int inc_seq[])
    {
        int inc = 0;    
        int max_inc_idx = 0;  
        int i,j,k,tmp;
    
        while (inc_seq[ max_inc_idx + 1 ] < N)    
            max_inc_idx++;  //找到最大的且小于N的那个增量 
    
        for (i = max_inc_idx; i >= 0; --i)
        {        
            inc = inc_seq[i];      
    #ifdef PRINT_PROCEDURE
                printf("-------- gap = %d--------\n",inc);
    #endif 
            for (j = inc; j < N; ++j) 
            {   
                if( A[j-inc] > A[j] )
                {
                    tmp = A[j];            
                    k = j - inc;          
                    while (k >= 0 && A[k] > tmp) 
                    {          
                        A[ k + inc ] = A[k];   // A[k]向后移动 inc个位置，腾出一个空位
                        k -= inc;     // 继续考察空位前面的元素 
                    }           
                    A[k + inc] = tmp;  // tmp 插入到k的后面 
    #ifdef PRINT_PROCEDURE
                    printf("[%d] insert to [%d]\n", j, k+inc);
    #endif 
                }
            } 
        }   
    } 
    
    
    int main(void)
    {
        printf("\n");
    
        int array[ARRAY_LEN]; 
    
        srand((unsigned int) time(NULL)); //设置随机数种子
    
        // 产生100个随机整数，范围在 [0, 100]
    
        for(int i=0; i<ARRAY_LEN; ++i)
        {
            array[i] = rand() % 101;
        }
        print_array(array,sizeof(array)/sizeof(array[0]),PRINT_GAP);
    
    
        int Sedgewick_seq[] = {
       1, 5, 19, 41, 109};
    
        shell_sort_improved(array, sizeof(array)/sizeof(array[0]),Sedgewick_seq);
    
        print_array(array,sizeof(array)/sizeof(array[0]),PRINT_GAP);
        return 0;
    }

运行结果如下图：  
![这里写图片描述][70]

【完】

# 参考资料 #

《数据结构与算法分析（原书第2版）》（机械工业出版社，2004）

[Link 1]: https://blog.csdn.net/longintchar/article/details/80259769
[70]: /images/20220524/699f3c7490e649b59742871c84f527cc.png