-1 
#include <iostream>
using namespace std;
void merge(int a[], int start, int pivot, int finish){
  int *tmp = new int[finish - start +1] ;
  int I = start ;
  int J = pivot +1 ;
  int K = 0 ;
  while((I <= pivot)&& ( J <= finish) ){
    if(a[I] < a[J]){
      tmp[K] = a[I] ; 
      K++ ; I++ ;
    }
    else{
      tmp[K] = a[J] ; K++ ; J++ ;

    }
  }
  if(I <= pivot){
    while(I <= pivot){
      tmp[K++] = a[I++] ;
    }
  }
  if( J<= finish){
    while(J<= finish){
      tmp[K++] = a[J++] ;
    }
  }
  for(K = start ; K <= finish ; K++) a[K] = tmp[K-start] ;
  delete []tmp ;
  return ;   

}

void mergesort(int a[], int start, int finish){
  if(start < finish){
    int pivot = (start + finish)/2 ;
    mergesort(a,start, pivot) ;
    mergesort(a, pivot+1, finish) ;
    merge(a, start, pivot, finish) ;
  }
}

int main(){
    int test[] = {4} ;
     mergesort(test,0, 1) ;

    for(int i = 0 ; i < sizeof(test)/sizeof(int); i++) cout<<" * " << test[i] ;
    cout<<endl ;
}

当我输出这个简单的测试时，它会打印“* 0”。为什么是零？它从何而来？该数组仅包含 4 个！

4

2 回答 2

1

您已经编写了合并排序例程，使得start和finish都是数组中的有效位置，但是您已经调用了例程，将finish其用作“结束后的一个”的索引。

我想你是想打电话mergesort(test, 0, 0);

0可能来自test[1]which 不是一个有效的索引，它实际上可以包含任何东西。它恰好0是小于4，因此您4将被移出数组的末尾。这是未定义的行为。

于 2013-11-13T22:37:30.553 回答
0

没关系，我想通了。调用 test[] = {4} 时；合并排序（测试，0,1）；

它应该是“合并排序（测试，0,0）”。原因是：参数'finish'应该是a.length-1。

测试[] = {4} ; //仅声明第一个尝试访问 test[45] 的元素，test[100] 会给出一些错误的数字 - 来自测试的“未知”部分。基本上，我希望同时处理开始和结束有效数字。test.len = 1 ，但它的索引为零，这就是为什么它本质上是从零到零- 没有其他数字可以寻找；如果我尝试访问 test[1] - 它会得到一些糟糕的未声明数字

于 2013-11-13T22:38:52.380 回答