为什么这个合并排序算法不能正常工作？

Question

我没有收到任何错误或警告。这是我的代码：

#include <iostream>

void merge(int arr[], int l, int m, int r);
void mergeSort(int arr[], int l, int r);

int main(){
    int arr[11] = {1, 9, 2, 5, 3, 10, 4, 8, 6, 7};

    mergeSort(arr, 0, 10);

    for(int i = 0; i < 11; i++){
        std::cout << arr[i] << "\t";
    }
    return 0;
}

void merge(int arr[], int l, int m, int r){
    int i = l;      // starting point of left subarray
    int j = m + 1;  // starting point of right subarray
    int k = l;      // starting point of temporary array
    int temp[11];
    while(i <= m && j <= r){
        if(arr[i] <= arr[j]){
            temp[k] = arr[i];
            i++;
        } else {
            temp[k] = arr[j];
            j++;
        }
        k++;
    }
    while(i <= m){
        temp[k] = arr[i];
        k++; i++;
    }
    while(j <= r){
        temp[k] = arr[j];
        k++; j++;
    }
    for(int s = l; s < 11; s++){
        arr[s] = temp[s];
    }
}

void mergeSort(int arr[], int l, int r){
    if(l < r) {
        int m = (l + r) / 2; // middle
        mergeSort(arr, l, m); // left subarray
        mergeSort(arr, m + 1, r); // right subarray
        merge(arr, l, m, r);
    }
}

这是我编译时得到的运行:

0 1 2 3 4 9 4199851 7208472 7667712 7669136 1996860265

左边好像排序好了——虽然原来的数组里没有0，然后就乱了，右边全是废话。

如果有人能帮助我，我将不胜感激 - 谢谢。

Answer 1

问题出在合并函数上。您必须从 l 循环到 r，inclusive 而不是 11。请查看参考代码以便更好地理解。

参考代码

#include <iostream>

void merge(int arr[], int l, int m, int r);
void mergeSort(int arr[], int l, int r);

int main(){
    int arr[11] = {1, 9, 2, 5, 3, 10, 4, 8, 6, 7};

    mergeSort(arr, 0, 10);

    for(int i = 0; i < 11; i++){
        std::cout << arr[i] << "\t";
    }
    return 0;
}

void merge(int arr[], int l, int m, int r){
    int i = l;      // starting point of left subarray
    int j = m + 1;  // starting point of right subarray
    int k = l;      // starting point of temporary array
    int temp[11];
    while(i <= m && j <= r){
        if(arr[i] <= arr[j]){
            temp[k] = arr[i];
            i++;
        } else {
            temp[k] = arr[j];
            j++;
        }
        k++;
    }
    while(i <= m){
        temp[k] = arr[i];
        k++; i++;
    }
    while(j <= r){
        temp[k] = arr[j];
        k++; j++;
    }
    for(int s = l; s <= r; s++){
        arr[s] = temp[s];
    }
}

void mergeSort(int arr[], int l, int r){
    if(l < r) {
        int m = (l + r) / 2; // middle
        mergeSort(arr, l, m); // left subarray
        mergeSort(arr, m + 1, r); // right subarray
        merge(arr, l, m, r);
    }
}

输出

0 1 2 3 4 5 6 7 8 9 10

为什么这个合并排序算法不能正常工作？

Why does this merge sort algorithm not work properly?

c++

mergesort