关于ShellSort希尔排序
来源：3-1 归并排序法 - Merge Sort
xm0516
2017-08-17
由于课程未给出希尔排序，我便尝试着写一写，花了一个下午效率很低，但是还是云里雾里的，有这么三个问题：
既然ShellSort的思想是对每个子序列再进行InsertionSort，那么第二层for循环里的i应该i<子序列.length 才对，但是在第三层for中j=j-dk似乎又向我说：没事，上面就写i<n就好。就是有这种直观感性的直觉。请问怎么理解二层中的i<n?子序列的长度明显不会是n，第一次选完步长一个子序列应该只有2个元素才对。
如果是奇数个的序列的话，肯定有落单的元素，代码是通过什么样的逻辑处理这个单独的人呢？
我的代码是根据课程中的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;
}
}1回答
-
由于希尔排序一般不会在面试中问到，所以在这个课程里由于时间限制，我选择不做详细介绍。希望感兴趣的同学自学完成：）
你的代码大体正确，有一个问题，第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。
如果对上面的过程还不理解，建议自己用一个小数据跟跟看，看看每一步数据是如何变化的：）加油！
462017-08-30
相似问题