我尝试实现合并排序，但无法找到我的代码的确切问题。程序没有显示错误，但我没有得到所需的输出

Question

尝试实现合并排序，下面是代码。如果有什么问题，请告诉我。我的合并功能是否有任何错误？无法指出我的代码中的确切问题。任何关于相同的帮助将不胜感激。

#include <iostream>
using namespace std;

Merge函数用于合并两个排序的数组

void merge(int arr[], int start, int mid, int end) {
    int n1 = mid - start + 1;
    int n2 = end - mid;
    
    int arr1[n1], arr2[n2];
    for (int i = 0; i < n1; i++) {
        arr1[i] = arr[start + i];
    }
    for (int j = 0; j < n2; j++) {
        arr2[j] = arr[mid + 1 + j];
    }

    int i;
    int j;
    int p;
    i = 0;
    j = 0;
    p = start;
    
    while (i < n1 && j < n2) {
        if (arr1[i] <= arr2[j]) {
            arr[p] = arr1[i];
            i++;
        } else {
            arr[p] = arr2[j];
            j++;
        }
        p++;
    }
    while (i < n1) {
        arr[p] = arr1[i];
        i++;
        p++;
    }

    while (j < n2) {
        arr[p] = arr2[j];
        i++;
        p++;
    }
}

递归调用Mergesort

void merge_sort(int arr[], int start, int end) {
    if (start >= end) {
      return;
    }
    if (start < end) {
        int mid = start + (end - 1) / 2;
        merge_sort(arr, start, mid);
        merge_sort(arr, mid + 1, end);
        merge(arr, start, mid, end);
    }
}

打印函数来打印数组

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

主要功能

int main() {
    int arr[] = { 6, 5, 12, 10, 9, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
    
    merge_sort(arr, 0, n - 1);
    cout << "The sorted array is: " << endl;
    printArray(arr, n);
}

Answer 1

代码中有两个错误:

> < li>

将中点计算为< code > int mid = start(end-1)/2；不正确。你应该写:

  int mid = start + (end - start) / 2;

在< code>merge的最后一个循环中，递增的是< code>i，而不是< code>j。注意，这个循环是多余的，因为< code>arr2的剩余元素已经在< code>arr的末尾。

您遵循mergesort实现中的经典约定，其中end是切片中最后一个元素的索引。此约定需要多次1/-1调整，很容易出错。

在数组索引以0开头的C语言和相关语言中，使用不同的约定更为习惯：将开始作为切片的第一个元素的索引，将结束作为最后一个元素后面的索引。这允许指定空接头并生成更干净的代码。

这是修改后的版本：

#include <iostream>

using namespace std;

// Merge function to merge the two sorted arrays
void merge(int arr[], int start, int mid, int end) {
    int n1 = mid - start;
    int n2 = end - mid;
    int arr1[n1], arr2[n2];

    for (int i = 0; i < n1; i++) {
        arr1[i] = arr[start + i];
    }
    for (int j = 0; j < n2; j++) {
        arr2[j] = arr[mid + j];
    }

    int i = 0;
    int j = 0;
    int p = start;
    
    while (i < n1 && j < n2) {
        if (arr1[i] <= arr2[j]) {
            arr[p] = arr1[i];
            i++;
        } else {
            arr[p] = arr2[j];
            j++;
        }
        p++;
    }
    while (i < n1) {
        arr[p] = arr1[i];
        i++;
        p++;
    }
    // the remaining elements from `arr2` are already in place in `arr`
}

// Calling mergesort recursively
void merge_sort(int arr[], int start, int end) {
    if (end - start > 1) {
        int mid = start + (end - start) / 2;
        merge_sort(arr, start, mid);
        merge_sort(arr, mid, end);
        merge(arr, start, mid, end);
    }
}

// Print function to print the array
void printArray(const int arr[], int size) {
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

// Main function
int main() {
    int arr[] = { 6, 5, 12, 10, 9, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
    
    merge_sort(arr, 0, n);
    cout << "The sorted array is: " << endl;
    printArray(arr, n);
    return 0;
}