Merge Sort算法未处理数组最后一个元素的问题排查求助

你的代码问题出在mergel函数的最后一步——将临时数组c的元素复制回原数组arr的循环逻辑错误。

问题分析 #

原代码中的复制循环：

for(i = low;i<k;i++){
    arr[i] = c[i];
}

临时数组c是从索引0开始存储合并后的元素的，而原数组需要从low位置开始覆盖。当low大于0时（比如处理数组后半段的子数组），i从low开始，此时i会远大于k（k是合并后的元素总数，等于high - low + 1），循环条件i < k直接不成立，导致临时数组里的排序结果根本没复制回原数组，这就解释了为什么最后一个元素1没被正确排序——它所在的子数组合并后的数据完全没更新到原数组里。

修复后的代码 #

只需要修改mergel函数的复制循环部分，让临时数组的每个元素对应到原数组的正确位置：

#include<bits/stdc++.h>
using namespace std;
void mergel(int arr[], int low, int mid, int high){
    int i = low;
    int j = mid+1;
    int k = 0;
    int c[50];
    while(i<=mid && j<=high){
        if(arr[i]<arr[j]){
            c[k] = arr[i];
            i++;
            k++;
        }
        else{
            c[k] = arr[j];
            j++;
            k++;
        }
    }
    while(i<=mid){
        c[k] = arr[i];
        k++;
        i++;
    }
    while(j<=high){
        c[k] = arr[j];
        k++;
        j++;
    }
    // 修正后的复制循环
    for(int m = 0; m < k; m++){
        arr[low + m] = c[m];
    }
}
void mergesort(int arr[], int low, int high){
    if(low<high){
        int mid = low + (high-low)/2;
        mergesort(arr,low,mid);
        mergesort(arr,mid+1,high);
        mergel(arr,low,mid,high);
    }
}
int main(){
    int arr[] = {8,2,4,7,9,1};
    int n = sizeof(arr)/sizeof(arr[0]);
    mergesort(arr,0,n-1);
    for(int i=0;i<n;i++){
        cout<<arr[i]<<" ";
    }
    return 0;
}

验证结果 #

修复后运行代码，输出会是：1 2 4 7 8 9，所有元素都被正确排序。

内容的提问来源于stack exchange，提问作者notaPROgrammer