我需要完成一个小作业，写一个简单的合并函数，其原型如下：
void merge(int a[], int left_low, int left_high, int right_low, int right_high)
为了简化，我们只考虑一个数组 a[]，并且 right_low = left_high + 1。最终的值将存储在传入的原始数组 a[] 中。对于一个包含数值 a[] = {1,3,10,4,7,8} 的数组，它看起来是这样的：
a = {1, 3, 10 , 4, 7, 8}
^ ^ ^ ^
left_low left_high right_low right_high
针对这项任务，我们需要通过一些测试。第一个测试是合并两个数组，第二个测试是老师自己编写的归并排序函数，他会在一些随机排序的数组上调用该函数。以下是我实现的merge()函数：
void merge(int a[], int left_low, int left_high,
int right_low, int right_high) {
int temp[right_high + 1]; // temporary array to store the result
int left_i = left_low, right_i = right_low, temp_i = 0;
// while the temporary array is not filled
while(temp_i != right_high + 1)
{
if(left_i == left_high + 1)
temp[temp_i++] = a[right_i++];
else if(right_i == right_high + 1)
temp[temp_i++] = a[left_i++];
else if(a[left_i] < a[right_i])
temp[temp_i++] = a[left_i++];
else
temp[temp_i++] = a[right_i++];
} // end while
for(int i = 0; i < temp_i; ++i)
a[i] = temp[i];
}
当他调用第一个测试函数，仅检查两个数组的合并时，我的函数可以正常工作，单个数组已经被排序。但是，当他调用他的merge_sort函数时，我得到了垃圾值。这里是他的测试函数：
template<class T>
void print (std::string label, T a[], int length, bool report_sorted) {
bool sorted = true;
std::cout << label;
for (int i=0; i<length; ++i) {
std::cout << a[i];
if (i == length-1)
std::cout << std::endl;
else {
std::cout << ", ";
if (a[i] > a[i+1])
sorted = false;
}
}
if (report_sorted)
std::cout << (sorted ? " Sorted" : " Not Sorted") << std::endl;
}
void shuffle(int values[], int length) {
std::vector<int> v_values;
for (int i=0; i<length; ++i)
v_values.push_back(values[i]);
std::random_shuffle(v_values.begin(),v_values.end());
for (int i=0; i<length; ++i)
values[i] = v_values[i];
}
//Recursive Merge Sort
template<class T>
void merge_sort(T a[], int low, int high) {
if (high - low < 1) //Base case: 0 or 1 value to sort -> sorted
return;
else {
int mid = (low + high)/2; //Split in 1/2
merge_sort(a, low, mid); //Recursively sort low to mid
merge_sort(a, mid+1, high); //Recursively sort mid+1 to high
merge(a, low,mid, mid+1,high); //Merge sorted parts of array
}
}
//Standard Merge Sort (calls a generalized one, with more parameters)
template<class T>
void merge_sort(T a[], int length) {
merge_sort(a, 0, length-1);
}
std::cout << "\n\nTesting merge in merge sort" << std::endl;
int test_merge_sort[10] = {1,2,3,4,5,6,7,8,9,10};
for (int i=0; i<5; i++) {
shuffle(test_merge_sort, 10);
print("\n Array before sort: ", test_merge_sort, 10, false);
merge_sort(test_merge_sort, 10);
print(" Array after sort: ", test_merge_sort, 10, true);
}
而且由于某种原因，我的输出结果看起来像这样：
Array before sort: 3, 9, 2, 5, 8, 4, 6, 10, 1, 7
Array after sort: -944749486, 4, 5439488, 0, 5443192, 5443196, 1975317641, -944749486, 4, 1995111146
Not Sorted
Array before sort: 1995111146, 1975317641, 4, 0, -944749486, 5443192, 5443196, 5439488, 4, -944749486
Array after sort: -944749486, 4, 5439488, 0, 5443192, 5443196, 1975317641, -944749486, 4, 1995111146
Not Sorted
Array before sort: -944749486, -944749486, 5443196, 4, 5439488, 1995111146, 5443192, 1975317641, 0, 4
Array after sort: -944749486, 4, 5439488, 0, 5443192, 5443196, 1975317641, -944749486, 4, 1995111146
Not Sorted
Array before sort: 1975317641, -944749486, 4, 4, 5439488, 5443192, 5443196, -944749486, 0, 1995111146
Array after sort: -944749486, 4, 5439488, 0, 5443192, 5443196, 1975317641, -944749486, 4, 1995111146
Not Sorted
Array before sort: -944749486, 5443192, 5443196, 1975317641, 4, 0, -944749486, 5439488, 1995111146, 4
Array after sort: -944749486, 4, 5439488, 0, 5443192, 5443196, 1975317641, -944749486, 4, 1995111146
Not Sorted
我的合并代码出了什么问题导致这种情况发生？
int a[]很容易误导人，它并没有将数组传递给函数，而是等同于int* a，也就是一个简单的指针，这也意味着修改内容会对调用者的数据造成改变。 - Ulrich Eckhardt