关于ShellSort希尔排序

Question

由于课程未给出希尔排序，我便尝试着写一写，花了一个下午效率很低，但是还是云里雾里的，有这么三个问题：

1. 既然ShellSort的思想是对每个子序列再进行InsertionSort，那么第二层for循环里的i应该i<子序列.length 才对，但是在第三层for中j=j-dk似乎又向我说：没事，上面就写i<n就好。就是有这种直观感性的直觉。请问怎么理解二层中的i<n?子序列的长度明显不会是n，第一次选完步长一个子序列应该只有2个元素才对。

2. 如果是奇数个的序列的话，肯定有落单的元素，代码是通过什么样的逻辑处理这个单独的人呢？

3. 我的代码是根据课程中的InsertionSort写的，我想知道到底对不对。。。测试了一下感觉好像没问题，但是不知道到底是不是没问题。

   
   

template<typename T>
void ShellSort(T arr[],int n){

    for (int dk = n/2; dk >=1; dk=dk/2)
    /*Shell排序,初始步长使之为序列长度的一般，也就是一开始分两组；
    往后步长自取一半，直到最后为1，对整个序列进行直接插入*/
    {
        for (int i = dk; i < n; i++)
        {
            T e = arr[i];
            int j;
            for (j = i; j > 0 && arr[j - dk] > e; j -= dk)
            {
                arr[j] = arr[j - dk];
            }
            arr[j] = e;
        }
    }

    for (int count = 0; count < n; count++)
    {
        cout << arr[count] << endl;
    }
}

Answer 1

liuyubobobo 2017-08-18 02:30:29

由于希尔排序一般不会在面试中问到，所以在这个课程里由于时间限制，我选择不做详细介绍。希望感兴趣的同学自学完成：）

你的代码大体正确，有一个问题，第12行，j>0应该改成j>=dk，才能保证访问arr[j-dk]不越界。完整的第12行的for循环应该是：

for (j = i; j >= dk && arr[j - dk] > e; j -= dk)

根据你提的问题，我觉得你对Shell Sort的理解是有问题的，但是能把代码写的这样正确，相当相当赞，说明调试工夫了得：）

简单回答你的问题如下：

首先，你在代码中的注释是有误的。初始步长dk是n/2，不是将整个数组分成了两组，而是分成了n/2组。比如8个元素：0 1 2 3 4 5 6 7，初始步长dk=4的话，是将这8个元素分成了4组，0 4; 1 5; 2 6; 3 7；从第8行起，是针对这4组数据进行插入排序。

在这里注意，我们不是先处理完一组再处理一组的，而是4组数据轮次处理的。依然以8个元素为例，我们的i从dk=4开始，是因为0 1 2 3分别是四组的第一个元素，在插入排序中第一个元素已经有序了，不用管。然后看i = 4的元素应该插入到0 4这组的哪里；之后看i = 5应该插入到1 5这组数据的哪里；之后看i = 6应该插入到2 6这组数据的哪里。。。 以此类推。通过这个描述，就能看到为什么i的终止条件是i<n，因为每一个元素都肯定属于某一组，我们需要处理每一个元素，用插入排序的思路将它放到这一组的相应位置。

以上的描述也解释了第三重for循环，j的变化为什么是j-=dk；因为j在遍历这一组的其他元素，步长是dk：）

至于落单的元素，完全不用特殊处理啊，只不过我们分组以后每组的元素个数不同而已。第8行i<n的终止条件已经保证了每个元素都会被处理。比如我们有9个元素0 1 2 3 4 5 6 7 8，初始步长dk=4，我们依然分成了4组：1 4 8；1 5; 2 6; 3 7。

如果对上面的过程还不理解，建议自己用一个小数据跟跟看，看看每一步数据是如何变化的：）加油！

• 提问者 xm0516 #1

  非常感谢！

• 提问者 xm0516 #2

  谢谢老师，我今天看归并，回头再来解决这个问题。学习之余，又有些问题请教
  
  1.今天的归并又有个小问题,就是创建辅助数组时它好像是不允许下标作变量。报错2466 cant allocate an array sized 0. 这个应该怎么办呢？
  2.我是考研学生，购买本课程觉得很值，对于这些内容的理解起到深化作用。学懂了代码再看题目觉得确实好做。想请问老师，练习这些代码对于复试机试会起到帮助吗？我想考FDU

• liuyubobobo 回复 提问者 xm0516 #3

  关于你提的归并的问题，可以参见这个问答：http://coding.imooc.com/learn/questiondetail/7964.html 但根据你给我的提示信息，我感觉不完全是这个问题。请检查你开辟空间所使用的变量是否为0。这个课程提供了完整的参考代码，在遇到问题时，请先实践在自己的机子上运转参考代码是否有问题，再比对自己的代码哪里和参考代码不同。参考代码地址：https://github.com/liuyubobobo/Play-with-Algorithms

点开查看后面3条评论