随笔 - 312, 文章 - 14, 评论 - 1393, 引用 - 0
数据加载中……

希尔排序(shellsort)算法实现

    希尔排序(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;
    
*= *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[] = {5316657766441110986};
    output_array(data, 
12);
    shellsort(data, 
12);
    output_array(data, 
12);
    
return 0;
}




Android开发完全讲义(第2版)(本书版权已输出到台湾)

http://product.dangdang.com/product.aspx?product_id=22741502



Android高薪之路:Android程序员面试宝典 http://book.360buy.com/10970314.html


新浪微博:http://t.sina.com.cn/androidguy   昵称:李宁_Lining

posted on 2008-05-15 22:01 银河使者 阅读(2368) 评论(1)  编辑  收藏 所属分类: algorithmC/C++

评论

# re: 希尔排序(shellsort)算法实现  回复  更多评论   

这是最标准的算法
2008-05-16 12:08 | 网上买书

只有注册用户登录后才能发表评论。


网站导航: