mooZHENQIANGgggg 2017-05-12 13:32 采纳率: 42.9%
浏览 6883
已采纳

归并排序比较次数问题

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

  • 写回答

1条回答 默认 最新

  • threenewbee 2017-05-12 16: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

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?