c++ - 降序合并

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

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 [i] MergeSort众生按降序排序，但是它会在数组的开头包含一些随机的大数。我真的不知道为什么会这样。

最佳答案

C ++中的数组从零开始。但是，您的代码愉快地访问了a[high]，该值传递了值12。因此，您可以无限制地访问。如果对数组进行升序排序，则会发生相同的错误，但是由于您不打印a[12]（您的output()函数使用的范围不包括n），因此您看不到它。

我强烈建议采用一种编程风格，其中的范围包括开始值和结束值。当然，无论如何我还是建议对范围而不是索引使用迭代器。对于这些而言，约定更为明显。

快速解决方案（不会改变MergeSort()排除最后一个元素的方式）是应用两个更改：

将MergeSort()中的终止检查更改为

if (1 < high - low)

用数组的最后一个元素调用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

关于c++ - 降序合并，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/48603424/

mergesort

c++ - 降序合并