这是一个SHELL排序法的例子,中间有点问题不懂//ntn 是数组的个数 for(gap = ntn /2; gap > 0; gap /=2) { for(i = gap; i < ntn; i++){ for(j = i-gap; j>=0; j-=gap){ 这里是比较交换的部分 } } }我
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/03 23:12:03
![这是一个SHELL排序法的例子,中间有点问题不懂//ntn 是数组的个数 for(gap = ntn /2; gap > 0; gap /=2) { for(i = gap; i < ntn; i++){ for(j = i-gap; j>=0; j-=gap){ 这里是比较交换的部分 } } }我](/uploads/image/z/13141273-49-3.jpg?t=%E8%BF%99%E6%98%AF%E4%B8%80%E4%B8%AASHELL%E6%8E%92%E5%BA%8F%E6%B3%95%E7%9A%84%E4%BE%8B%E5%AD%90%2C%E4%B8%AD%E9%97%B4%E6%9C%89%E7%82%B9%E9%97%AE%E9%A2%98%E4%B8%8D%E6%87%82%2F%2Fntn+%E6%98%AF%E6%95%B0%E7%BB%84%E7%9A%84%E4%B8%AA%E6%95%B0+for%28gap+%3D+ntn+%2F2%3B+gap+%3E+0%3B+gap+%2F%3D2%29+%7B+++++for%28i+%3D+gap%3B+i+%3C+ntn%3B+i%2B%2B%29%7B++++++++for%28j+%3D+i-gap%3B+j%3E%3D0%3B+j-%3Dgap%29%7B++++++++%E8%BF%99%E9%87%8C%E6%98%AF%E6%AF%94%E8%BE%83%E4%BA%A4%E6%8D%A2%E7%9A%84%E9%83%A8%E5%88%86++++++++%7D++++%7D+%7D%E6%88%91)
这是一个SHELL排序法的例子,中间有点问题不懂//ntn 是数组的个数 for(gap = ntn /2; gap > 0; gap /=2) { for(i = gap; i < ntn; i++){ for(j = i-gap; j>=0; j-=gap){ 这里是比较交换的部分 } } }我
这是一个SHELL排序法的例子,中间有点问题不懂
//ntn 是数组的个数
for(gap = ntn /2; gap > 0; gap /=2) {
for(i = gap; i < ntn; i++){
for(j = i-gap; j>=0; j-=gap){
这里是比较交换的部分
}
}
}
我不明白的地方是,为什么要j -= gap,这样一来,不是有了很多重复的比较, 比如说
i = 5, gap=1, 这时候j从4开始,比较位置4和5,然后j -= gap,这时候j=3,比较3和4的位置,可是这之前在i = 4的时候,已经比较过了啊
请高人帮助!
这是一个SHELL排序法的例子,中间有点问题不懂//ntn 是数组的个数 for(gap = ntn /2; gap > 0; gap /=2) { for(i = gap; i < ntn; i++){ for(j = i-gap; j>=0; j-=gap){ 这里是比较交换的部分 } } }我
你好,希尔算法的基本思想是,利用一个增量序列,让待排序数组逐渐有序.
针对上面的算法,其实当gap等于1的时候,shell算法实际都退化成了简单插入排序.
至于楼主针对上面的算法提出的问题,的确,数组的3、4位置一定会比较多次,但是,有可能的是这两个位置的实际数值,已经不同.因为,先后两次比较的时候,整个待排序数组的位置已经有了改变.
不过,楼主上面的希尔算法可以进一步改进.让其减少无效的比较次数.