这个归并排序算法有什么问题？

Question

有人能告诉我这段代码有什么问题吗？此代码是使用合并排序对数组中的一组元素进行排序。

#include<iostream>

void merge(int arr[], int left, int mid, int right){
    int left_ptr = left;
    int right_ptr = mid + 1;
    int size = right - left + 1;       
    int temp[size];
    int k = left;

    while (left_ptr <= mid && right_ptr <= right)
    {
        if(arr[left_ptr] <= arr[right_ptr]){
            temp[k] = arr[left_ptr];
            left_ptr++;
            k++;
        }
        else{
            temp[k] = arr[right_ptr];
            right_ptr++;
            k++;
        }
        
    }

    while (left_ptr <= mid)
    {
        temp[k] = arr[left_ptr];
        left_ptr++;
        k++;
    }

    while (right_ptr <= right)
    {
        temp[k] = arr[right_ptr];
        right_ptr++;
        k++;
    }
    
    for (int i = left_ptr; i < k; i++)
    {
        arr[i] = temp[i];
    }
    
}

void mergeSort(int arr[], int left, int right){
    int mid;
    if (left < right)
    {
        mid = (right + left)/2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
    
}
int main(){
    int arr[] = {45,8,9,7,4,58,2,34,2,58}; 
    std::cout << arr << std::endl; 
    int size = sizeof(arr)/sizeof(int);
    mergeSort(arr, 0, size - 1);
    for (int i = 0; i < size; i++)
    {
        std::cout << arr[i] << "    ";
    }

    std::cout << std::endl;
    
}

我用很多在线代码仔细检查了它，我没有看到任何错误...你认为哪里出了问题？我尝试使用就地数组（类似于快速排序）来实现它。

Answer 1

我发现代码中有两个可能的错误：

在 merge 中声明 int temp[size]; 无效，因为 size 不是常量。您将需要动态分配数组。

其次，在 merge 函数的最后一段（for 循环）中，您初始化 i = left_ptr。但是，在此之前 left_ptr 被设置为等于 mid。我相信你真的想初始化 i = left.

编辑：刚刚注意到：temp 不一定要从 arr 的开头开始。我的意思是，temp 的每个元素都映射到 arr 的特定元素，但是您的代码假设在几个地方，temp[0] 映射到 arr[0]，这是不正确的（temp[0] 实际上映射到 arr[right]）。有两种方法可以解决这个问题。

您可以修复基于此假设的片段。在最后的 for 循环中使用 arr[i + right] = temp[i] 而不是 arr[i] = temp[i]，并将 k 初始化为零。

第二个选项是，不是在每次调用 merge 中创建和删除 temp，而是将其创建为大小等于 arr 并在算法的整个执行过程中保留它（这可以通过在算法外部创建它并将其传递给对 merge 或 MergeSort 的每次调用来完成）这样，等偏移假设实际上是正确的。

Answer 2

这是您的代码错误的列表。我在这里泛指“错误”。对于每一段代码，我的主要批评是基于风格而不是“正确性”，其中旨在使正确性更容易被发现的风格。

在此过程中，其中一种风格批评导致发现了看起来像错误的东西。

void merge(int arr[], int left, int mid, int right){

您正在使用 int 来引用数组中的偏移量。
您正在使用 int[] 参数，这是 int* arr 的旧 C 语法。改用 std::span 之类的东西。

进行中：

 int left_ptr = left;

如果您的目标是保留原始参数并处理副本，请制作原始参数 const 这样就不必证明它们在函数体中没有发生变化。

int right_ptr = mid + 1;

您有名为 _ptr 的变量，它们不是指针。

int size = right - left + 1;

您似乎没有使用半开区间。使用并学习使用半开区间。它们在 C++ 中是常规的，它们确实摆脱了很多 fence-post 更正代码。

int temp[size];

这不符合 C++。实际上，即使在支持此功能的编译器上，许多 C++ 实现的堆栈也比您可能想要排序的数组内存小得多。这会导致您的代码炸毁堆栈。

正确性比性能更重要。在堆栈上创建动态大小的对象会导致程序出现未定义的行为或在其他合理的输入上崩溃。

int k = left;

这个变量没有描述它的作用。

while (left_ptr <= mid && right_ptr <= right)
while (left_ptr <= mid)
while (right_ptr <= right)

这些循环中有很多代码重复。

DRY - 不要重复你自己。在这里，如果任何一个重复中有错误，如果你 DRY 这个错误将在所有用途中出现并且更容易被发现。这里有很多方法可以 DRY（lambda、辅助函数、稍微复杂一点的分支和一个循环）；使用其中之一。

for (int i = left_ptr; i < k; i++)
{
    arr[i] = temp[i];
}

看起来像是手动标准副本？看起来它也有一个错误，因为当然手动重新实现 std 副本意味着你做错了。

void mergeSort(int arr[], int left, int right){

同样，传统的 C 风格数组传递。

    int mid;

无需初始化就无需声明。将声明尽可能靠近它们的首次使用点，并尽快让它们脱离范围。

    if (left < right)
    {
        mid = (right + left)/2;

制作这个 int mid =.

        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

闭区间如何让你不得不做烦人的围栏的例子posting。

        merge(arr, left, mid, right);

mergeSort(arr, 0, size - 1);

另一个栅栏post +/- 1 这里。

这个归并排序算法有什么问题？

What is wrong with this merge sort algorithm?

c++

sorting

algorithm

mergesort

c++11