希尔排序(shellsort)算法实现-阿里云开发者社区

希尔排序(shellsort)算法实现

2008-05-15 781

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 希尔排序(shellsort)又叫增量递减(diminishing increment)排序，是由D.L. Shell发明的，这个算法是通过一个逐渐减小的增量使一个数组逐渐趋近于有序从而达到排序的目的。

    希尔排序(shellsort)又叫增量递减(diminishing increment)排序，是由D.L. Shell发明的，这个算法是通过一个逐渐减小的增量使一个数组逐渐趋近于有序从而达到排序的目的。

      假设有一个数组int data[16] = {...}。首先将这个增量设为16 / 2 = 8，这样就将这个数组分成了8个子数组，它们的索引是0, 8    1, 9   2, 10等等。对这些子数组进行排序。然后再使增量为8 / 2 = 4，这样就将原数组分成了4个子数组，它们的索引分别是0, 4, 8, 12    1, 5, 9, 13等等。再对这四组数进行排序，直到增量为1。
     以上所描述的增量递减只是一种方法，这种方法并不是最有效率的。如f(n) = 3 * f(n - 1) + 1 f(1) = 1   (..., 121, 40， 13, 4, 1)就比上面的取增量的方法好。这种方法的时间复杂度是 O(n ^1.5)。

算法如下

#include < stdio.h >

void output_array( int data[], int n)
{
     int i;
     for (i = 0 ; i < n; i ++ )
        printf( " %d " , data[i]);
    printf( " /n " );
}
void swap( int * a, int * b)
{
     int x;
    x = * a;
     * a = * b;
     * b = x;
}
void insertion_sort( int data[], int n, int increment)
{
     int i, j;
     for (i = increment; i < n; i += increment)
         for (j = i; j >= increment && data[j] > data[j - increment]; j -= increment)
            swap( & data[j], & data[j - increment]);
}
void shellsort( int data[], int n)
{
     int i, j;
     for (i = n / 2 ; i > 2 ; i /= 2 )
         for (j = 0 ; j < i; j ++ )
            insertion_sort(data + j, n - j, i);
    insertion_sort(data, n, 1 );
}
int main()
{
     int data[] = { 5 , 3 , 1 , 665 , 77 , 66 , 44 , 11 , 10 , 9 , 8 , 6 };
    output_array(data, 12 );
    shellsort(data, 12 );
    output_array(data, 12 );
     return 0 ;
}

国内最棒的Google Android技术社区（eoeandroid），欢迎访问！

《银河系列原创教程》发布

《Java Web开发速学宝典》出版，欢迎定购