0

我做了一个 MergeSort 函数，但它打印出奇怪的数字。当我传入 int arr[12]={5,3,2,7,6,8,9,6,3,5,2,1}; 我得到“123500085000”。我试图在调试器中跟踪我的数组，但对它有点缺乏经验。当我“观察”数组变量时，当它被传递给函数时，值会变成地址。谁能指出我的功能出了什么问题的正确方向？

#include <iostream>
using namespace std;



void merge(int arr[], int aux[], int low, int mid, int high)
{
    int leftStart = low;
    int rightStart = mid+1;
    int auxIndex = low;
    int start = low;

while(leftStart<=mid && rightStart<= high)
{
    if(arr[leftStart]>=arr[rightStart])
    {
        aux[auxIndex++] = arr[rightStart++];
    }
    else
        aux[auxIndex++] = arr[leftStart++];
}
if(leftStart>mid)
{
    for(;rightStart<=high; rightStart++)
    {
        aux[auxIndex] = arr[rightStart];
    }
}
if(rightStart>high)
{
    for(;leftStart<=mid; leftStart++)
    {
        aux[auxIndex] = arr[leftStart];
    }
}
for(; start <= high; start++)
    arr[start]=aux[start];
}

void mergeSort(int arr[], int aux[], int low, int high)
{
    int mid;
    if(low<high)
    {
    mid=(low+high)/2;
    mergeSort(arr, aux, low, mid);
    mergeSort(arr, aux, mid+1, high);
    merge(arr,aux, low, mid, high);
    }
}


int main() {
int arr[12]={5,3,2,7,6,8,9,6,3,5,2,1};
int aux[12]={0,0,0,0,0,0,0,0,0,0,0,0};
mergeSort(arr, aux, 0, 11);
for(int i = 0; i<12; i++)
    cout<<arr[i];
    cout<<endl;
for(int i = 0; i<12; i++)
    cout<<aux[i];
    return 0;
}
4

1 回答 1

2

您在代码中的问题在于以下几点：

if(leftStart>mid)
{
  for(;rightStart<=high; rightStart++)
  {
    aux[auxIndex] = arr[rightStart]; //wrong
    aux[auxIndex++] = arr[rightStart];
  }
}

if(rightStart>high)
{
  for(;leftStart<=mid; leftStart++)
  {
    aux[auxIndex] = arr[leftStart]; //wrong again
    aux[auxIndex++] = arr[leftStart];
  }
}

您必须增加aux数组的索引。更正后，我得到：

1 2 2 3 3 5 5 6 6 7 8 9

1 2 2 3 3 5 5 6 6 7 8 9

通过在两个数组的每个元素后添加一个空格。

于 2013-03-21T21:16:28.760 回答