随感而发

杂七杂八

统计

留言簿(13)

阅读排行榜

评论排行榜

希尔排序

今天学习了希尔排序,他的主要思想借用了合并排序的思想。不过他不是左边一半右边一半,而是按照步长来分,随着步长减少,分成的组也越少。然后进行各组的插入排序。主要思路就是这样,我在百度百科的博客园找到了其相关学习资料,附上连接:

http://baike.baidu.com/view/178698.htm

http://www.cnblogs.com/nokiaguy/archive/2008/05/16/1199359.html

所以就不用写思路了哦,真笨,语文也得好好学学,不然组织语言的能力太差了。呵呵。

奉上源代码(因为是自己写的,所以还是贴一下):

#include <stdio.h>
#include 
<stdlib.h>

//对单个组排序
int SortGroup(int* pnData, int nLen, int nBegin,int nStep)
{
    
for (int i = nBegin + nStep; i < nLen; i += nStep)
    {
        
//寻找i元素的位置,
        for (int j = nBegin; j < i; j+= nStep)
        {
            
//如果比他小,则这里就是他的位置了
            if (pnData[i] < pnData[j])
            {
                
int nTemp = pnData[i];
                
for (int k = i; k > j; k -= nStep)
                {
                    pnData[k] 
= pnData[k - nStep];
                }
                pnData[j] 
= nTemp;
            }
        }
    }
    
return 1;
}
//希尔排序, pnData要排序的数据, nLen数据的个数
int ShellSort(int* pnData, int nLen)
{
    
//以nStep分组,nStep每次减为原来的一半。
    for (int nStep = nLen / 2; nStep > 0; nStep /= 2)
    {
        
//对每个组进行排序
        for (int i = 0 ;i < nStep; ++i)
        {
            SortGroup(pnData, nLen, i, nStep);
        }
    }

    
return 1;
}

int main()
{
    
int nData[10= {4,10,9,8,7,6,5,4,3,2};    //创建10个数据,测试
    ShellSort(nData, 10);        //调用希尔排序

    
for (int i = 0; i < 10++i)        
    {
        printf(
"%d ", nData[i]);
    }

    printf(
"\n");
    system(
"pause");
    
return 0;
}

posted on 2009-04-25 17:02 shongbee2 阅读(12101) 评论(1)  编辑 收藏 引用 所属分类: 数据结构和算法

评论

# re: 希尔排序 2012-08-30 10:45 wood

“他的主要思想借用了合并排序的思想。不过他不是左边一半右边一半,而是按照步长来分,随着步长减少,分成的组也越少”

非常感谢 我似乎知道希尔排序到底快在哪里了。。。(貌似是他类似一个自底向上的归并排序)  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理