波斯马BOSSMA Information Technology

C#排序算法之希尔排序(shellsort)

发布时间:2010年9月10日 / 分类:DOTNET / 9,899 次浏览 / 评论

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

希尔排序对数据进行分组,每个分组进行直接插入排序。
增量是每个分组中紧挨着的前后两个元素的距离,或者可以理解成每个分组的大小。
假设待排序文件有10个记录,其关键字分别是:
49,38,65,97,76,13,27,49,55,04
增量序列的取值依次为:
5,3,1

/// <summary>
        /// 希尔排序
        /// </summary>
        static void ShellSort(int[] intArr)
        {
            int numberOfLoop = 0;
            int numberOfSwap = 0;

            //每组数量,即增量
            int numberOfPerGroup;

            //获取初始增量值
            //关于最优增量值如何得出,没有找到可用的资料,这里参考网上常见的数值
            for (numberOfPerGroup = 1; numberOfPerGroup <= intArr.Length / 9; numberOfPerGroup = 3 * numberOfPerGroup + 1) ;

            //增量递减
            for (; numberOfPerGroup > 0; numberOfPerGroup = numberOfPerGroup / 3)
            {
                numberOfLoop++;

                //这里就是直接插入排序了
                for (int i = 0; i < intArr.Length; i += numberOfPerGroup)
                {
                    int j;
                    int temp = intArr[i];

                    for (j = i; j >= numberOfPerGroup; j -= numberOfPerGroup)
                    {
                        numberOfLoop++;

                        if (intArr[j - numberOfPerGroup] > temp)
                        {
                            numberOfSwap++;
                            intArr[j] = intArr[j - numberOfPerGroup];
                        }
                        else
                        {
                            break;
                        }
                    }

                    numberOfLoop++;
                    intArr[j] = temp;
                }
            }
本博客所有文章如无特别注明均为原创。
复制或转载请以超链接形式注明转自波斯马,原文地址《C#排序算法之希尔排序(shellsort)

关键字:

建议订阅本站,及时阅读最新文章!
【上一篇】 【下一篇】

发表评论