这是一个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/11/08 03:26:46
这是一个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位置一定会比较多次,但是,有可能的是这两个位置的实际数值,已经不同.因为,先后两次比较的时候,整个待排序数组的位置已经有了改变.
不过,楼主上面的希尔算法可以进一步改进.让其减少无效的比较次数.