波斯马BOSSMA Information Technology

希尔排序(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;
                }
            }

关键字: shellsort 希尔排序 排序算法