2 xxxxxxxxx0009 xxxxxxxxx0009 于 2017.05.12 21:32 提问

归并排序比较次数问题

第二趟排序,为什么前半部分比较次数和后半部门比较次数都是3,是那些数在比较,求大神。百度了很久都没找到图片说明

1个回答

caozhy
caozhy   Ds   Rxr 2017.05.13 00:18
已采纳

1 3
1 4
首先1和1比,得到1 1
然后3和1(这里的1是指第二个1)比,得到1 1 3
最后3和4比,得到1 1 3 4
后一个类似

再举一个例子
1 3 6和2 7 8归并
首先1 2比得到1 2(此时可以得知第二个数组没有比2小的数字,但是第一个数组不一定,所以下面用第一个数组的3和2比)
然后3 2比,得到1 2 3(此时可以得知第一个数组没有比3小的,但是第二个数组不一定,所以下面用3 7比)
然后3 7比,得到1 2 3 7
然后6 7比,得到1 2 3 6 7(此时第一个数组比完了,不会再有比6大的,输出第二个数组剩下的)
结束,得到1 2 3 6 7 8

xxxxxxxxx0009
xxxxxxxxx0009 回复caozhy: 谢谢,很详细
3 个月之前 回复
Csdn user default icon
上传中...
上传图片
插入图片