c++ - 降序合并排序

Question

我写了一些代码来执行降序合并排序。

void Merge(int a[], int low, int high, int mid)
{

int i=low,j=mid+1,k=0;
int temp[high-low+1];

while(i<=mid && j<= high)
{
    if(a[i]>a[j])               //comparison step
        temp[k++]=a[i++];

    else
        temp[k++]=a[j++];

}

while(i<=mid)
    {
        temp[k++]=a[i++];
    }

while(j<=high)
    {
        temp[k++]=a[j++];
    }

for(i=low;i<=high;i++)
{

    a[i]=temp[i-low];

}


return;
}


void MergeSort(int a[],int low, int high)
 {
int mid;

if(low<high)
{
    mid=(low+high)/2;

    MergeSort(a,low,mid);
    MergeSort(a,mid+1,high);

    Merge(a,low,high,mid);
}

return;
}


void output(int *a,int n)
{
 for(int i=0;i<n;i++)
 {
     cout<<a[i]<<"\t";
 }
}

int main()
{
 int n=12;
 int a[n]={23,45,1,2,8,0,9,56,73,5070,20,16};
 MergeSort(a,0,n);
 output(a,n);

}

此代码在顺序为升序时完美运行，即。比较是 a[i] < a[j]

然而，通过使用 a[j] > a[i] MergeSort 进行降序排序，但它会在数组的开头包含一些随机的大数。我真的不明白为什么会这样。

Answer 1

C++ 中的数组是从零开始的。但是，您的代码很乐意访问 a[high]它传递了值 12 .因此，您获得了越界访问权限。如果您对数组进行升序排序但由于您不打印 a[12]，则会发生同样的错误。 (你 output() 函数使用了不属于 n 的范围)你看不到它。

我强烈建议采用范围包含开始值和不包含结束值的编程风格。当然，我也建议对范围使用迭代器而不是索引。对于这些约定更为明显。

快速修复(不会改变您的 MergeSort() 排除最后一个元素的方式)是应用两个更改:

1. 在 MergeSort() 中更改终止检查成为

   if (1 < high - low)
   

2. 调用 MergeSort()与数组的最后一个元素

   MergeSort(a, 0, n - 1);
   

请注意可变大小的内置数组，如 int temp[high - low + 1] 不是标准 C++ 的一部分，尽管某些编译器将它们作为扩展支持(例如 g++)。对于更大的数组，它们也会导致问题，因为它们必然会溢出堆栈。你最好使用 std::vector<int> :

std::vector<int> temp(high - low + 1);

对于测试数组，您可以使用静态大小的数组，编译器确定大小并让编译器计算出数组:

 int a[]={23,45,1,2,8,0,9,56,73,5070,20,16};
 int n = std::end(a) - std::begin(a); // need <iterator> to be included