归并排序数组问题


0


归并排序完毕后一定要把临时数组的元素都复制到原数组嘛(⊙_⊙)？好像最后直接输出临时数组也能过

望大佬指教



提问于3天前
822
如果没有复制到原数组的话， 你进行合并操作时候，左右两边的数组不是有序的啊。 –  哈哈_8   3天前
@哈哈_8:  已经归并完了呀 –  晨曦时雨   3天前
@晨曦时雨:  如果不复制，递归完的原数组就没变啊。 –  哈哈_8   3天前
@哈哈_8:  那要是递归完以后直接使用临时数组行吗 –  晨曦时雨   2天前
@晨曦时雨:  因为你还是往临时数组里合并， 就算你左右两个临时数组是有序的， 往里面合并的时候，会改变原来数的大小。 就不对了 –  哈哈_8   2天前
@哈哈_8:  比如 [4 6 9] 和[1 3] 合并 因为1比较小 ，就变成了[1 6 9] [1 3] ， 除非你保证你合并过去的数组空间不一样 –  哈哈_8   2天前
https://www.acwing.com/activity/content/code/content/895110/ 麻烦您看一下我的这篇打卡，我所说的临时数组是这段代码的tmp[]，到最后直接输出tmp[]也能AC –  晨曦时雨   2天前


1 个问答


1

直接输出临时数组当然能AC,但复制不能省,因为下一次递归里面

    while(i<=mid&&j<=r)//合二为一
    {
        if(q[i]<=q[j])
            tmp[k++]=q[i++];
        else
            tmp[k++]=q[j++];
    }

这里面用到了q,不复制的话q是不会变的,那就肯定错

但也不能不用q,因为它在合二为一的时候用一个数组可能会冲突

直接输出tmp能AC是因为最后tmp和q存的是一个东西,当然就可以输出tmp

回答于1天前
9817
@晨曦时雨:  不谢hh –  wx090708   1天前
噢，谢谢您，明白了，感谢 –  晨曦时雨   1天前
我来回答