FunctionGHW

立志成为真正程序员的码农,伪全栈,目前主要写C#

希尔排序(Shell Sort)算法学习

FunctionGHW posted @ 2013年11月03日 01:07 in 算法学习 with tags 排序 shell sort , 2019 阅读

希尔排序是对插入排序的改进。 如果把排序的过程看作消除序列中 逆序对 的过程,那么排序的最终结果就是序列中没有逆序对。 普通的插入排序每次交换相邻元素,一次交换只能消除一个逆序对; 希尔排序允许交换相距一定间隔的元素,一次交换可以消除多个逆序对,因此速度更快。

算法步骤

希尔排序要使用一个序列{\(h_1\), \(h_2\),..., \(h_k\), }, 称为增量序列,其中\(h_1\)必须是1,如果\(i \lt j,则h_i \lt h_j\), 还有就是每一项都不大于序列的长度。好的增量序列能显著改善算法性能。

算法的具体步骤描述如下:

  1. 取增量\(h_i\),其中i = k,即增量序列中的最后一项。
  2. 增量\(h_i\)逻辑上把待排序序列分成\(h_i\)个子序列, 每个子序列由所有相距\(h_i\)的元素组成。
  3. 对每个子序列进行插入排序。这个排序步骤在Sedgewick的《Algorithms,4th edition》中叫做h-sort。
  4. 令i=i - 1,重复2,3步骤,直到\(h_i\) = 1。

 

在最后增量为1的时候进行的就是普通的插入排序,此时大部分逆序都已经被消除了, 因此这次插入排序的速度非常快。一般的实现中可以把增量序列单独作为数组存放,也可以使用表达式"生成"。

下面实现(C语言)改编自《Algorithms,4th edition》中的实现:

/*希尔排序*/
void shell_sort(int arr[], int length)
{
    int h = 1, i, j;
    // 计算增量的最大值,不超过数组长度的1/3.
    while (h < length / 3)
    {
        // 这个就是"生成"增量序列的表达式
        h = 3 * h + 1; // 1, 4, 13, 40, 121, 364, 1093...
    }

    while (h >= 1)
    {
        // h-sort 步骤
        for (i = h; i < length; i++)
        {
            // 对一个"子序列"进行插入插排
            for (j = i; j >= h; j -= h)
            {
                if (arr[j] < arr[j - h])
                {
                    int tmp = arr[j];
                    arr[j] = arr[j - h];
                    arr[j - h] = tmp;
                }
            }
        }
        h = h / 3;
    }
}
                

增量序列的好坏直接影响算法的性能。 有许多已知的比较好的序列,目前最好增量序列据说是由Sedgewick提出的:{1, 5, 19, 41, 109,...}, 其中有些项由\(9 * 4^i - 9 * 2^i + 1\)计算得到,另一些由\(4^i - 3 * 2^i + 1\)计算得到。

希尔排序的代码实现并不复杂,但是其时间复杂度的分析就相当复杂。 希尔排序的时间复杂度直接依赖于增量序列的选择。对希尔排序的的平均情形的分析, 除了最平凡的一些增量序列之外,是一个长期未能解决的难题。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter