-1 
 void merge(int *a1, int *a2, int *a3, int s1, int s2, int s3){
     s2 -=1;
     int track =0;
     s3-=1;
     int p2=0;
     int p3=0;
     while(p2<s2 && p3 <s3){
         if(a2[p2]<a3[p3])
             a1[track++]=a2[p2++];
         else
             a1[track++]=a3[p3++];
     }
     while(p2<s2) a1[track++]=a2[p2++];
     while(p3<s3) a1[track++]=a3[p3++];
 }


 void msort(int *array, int n){
     if(n<=1) return;
     int a1_size = n/2;
     int a2_size = n-n/2;
     int a1[n/2];
     int a2[n-n/2];
     for(int i=0;i<n/2;i++){
    a1[i] = array[i];
     }
     for(int i=0,j=n/2;j<n;i++,j++){
         a2[i] = array[j];
     }
     msort(a1, n/2);
     msort(a2, n-n/2);
     merge(array, a1, a2, n, a1_size, a2_size);
 }

 int main(){
     int a[]={1,2,1,2,3,94,5,67};
     msort(a,8);
     for(int i=0;i<8;i++)
         cout << a[i] << endl;
}

这是我的代码，我希望它会返回一个排序数组。我知道问题在于将数组的地址传递给合并将修改数组内的数据，从而影响结果。我尝试了很长时间，但仍然无法弄清楚如何修改它。有人可以给我提示或帮助吗？

4

1 回答 1

2

问题出在s2 -= 1ands3 -= 1语句中。你为什么这样做？从零开始迭代数组的标准习惯用法index是计算 while index < length，而不是 while index < length-1。

其他几点注意事项：

  • 你分配了很多额外的内存（n*log(n) ints），大部分时间都没有使用。只需要在 inside分配，merge那样任何时候最多n分配int。
  • 学习使用std::vector和/或迭代器范围而不是 C 样式的数组
于 2012-07-09T07:07:17.293 回答