当前位置：首页 → 问答吧 → 请教一下希尔排序问题

请教一下希尔排序问题

时间：2010-07-21

来源：互联网

请教一下希尔排序的问题：
我们
以5,3,1为步长做插入
按照书上所讲，5- 排序后，3-排序不会影响5-排序的结果，

但是我以
20,1,2,3,4,19,6,7,5,8,40,11,12 为例，则其以5- 排序结果为
19,1,2,3,4,20,6,7,5,8,40,11,12，做3- 排序后
3,1,2,6,4,5,8,7,11,12,40,20,19，很明显下一次排序会影响到上一次排序的结果，这和书上所讲是矛盾的，

附：数据结构与算法分析，167页希尔排序的一个重要性质是一个k次排序在 k-1 次排序后保持k次排序性。

不理解，请教了。

作者: tianhailong 发布时间: 2010-07-21

不理解。。。

作者: donglongchao 发布时间: 2010-07-21

摘录一下原文，对应的书应该是《Data Structures and Algorithm Analysis in C (2nd Edition) 》没错

An important property of Shellsort (which we state without proof) is that an hk-sorted file that is then hk-1-sorted remains hk-sorted.

复制代码

看了原文这句话，然后我的理解是以5-排序和3-排序为例，所有5-排序中的数对（间隔是5的）的顺序不会在3-排序中被改变，而不是指整体的序列，因为5-排序之后的序列并非最终序列，所以顺序必然还会再次变化的，然而经由5-排序处理后的数对，如19和20还有3和5，在以后的过程中总是会保证19在20之前，3在5之前，同样道理3-排序后也保证所有间隔3的数对的顺序不会改变，当然，最终1-排序后的任意数对之间的位置就是最终位置了

作者: daybreakcx 发布时间: 2010-07-21

你看的啥书？

作者: lenovo 发布时间: 2010-07-21

回复 daybreakcx

20,1,2,3,4,19,6,7,5,8,40,11,12 初始序列
19,1,2,3,4,20,6,7,5,8,40,11,12 经过5 排列后，19在20之前
3,1,2,6,4,5,8,7,11,12,40,20,19，经过3 排列后，19在20之后，

就是说上一次的排列形成的19，20的想对关系，在本次排列结束后发生了改变，和你所说是不一致的
我个人理解也是像你讲的一样

作者: tianhailong 发布时间: 2010-07-21

请教一下希尔排序问题

热门阅读

热门下载