C语言归并排序实现出现重复元素且部分元素丢失问题求助

问题现象 #

用C语言实现基础归并排序后，运行结果出现连续重复元素，部分元素完全缺失。例如输入6 5 4 3 2 1 8 9，输出为1 1 3 3 3 3 8 9。

问题代码 #

// sorting.h 中的函数
void merge_sort(int *arr, int left, int right){
    if (left<right){
        int mid = left + (right-left)/2;

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

        merge(arr, left, mid, right);
    }
}

void merge(int *arr, int left, int mid, int right){
    int length1 = mid - left + 1;
    int length2 = right - mid;
    int left_arr[length1];
    int right_arr[length2];

    int i, j;
    for (i=0; i<length1; i++)
        left_arr[i] = arr[left+i];
    for (j=0; j<length2; j++)
         right_arr[j] = arr[mid + 1 + j];

    i=0;
    j=0;
    int k = left;
    while(i<length1 && j<length2){
        if (left_arr[i]<=right_arr[j]){ 
            arr[k] = left_arr[i]; 
            i++;
        }
        else{
            arr[k] = right_arr[j]; 
            j++;
        }
        k++;
    }
    while (j<length2){
        arr[k] = right_arr[j];
        j++;
        k++;
    }
}

void print_array(int array[], int length){
    for (int i=0; i<length; i++)
        printf("%d ", array[i]);   
}

// 主文件
#include <stdio.h> 
#include <stdlib.h>
#include "sorting.h"

#define ARR_LENGTH 8

int main(int argc, char *argv[]){
    int arr[ARR_LENGTH];
    if (argc!=ARR_LENGTH+1)
        printf("Too many or too few arguments passed.");
    else{
        for (int i=1; i<=ARR_LENGTH; i++)
            arr[i-1]=strtod(argv[i], NULL);
        merge_sort(arr, 0, ARR_LENGTH-1);
        print_array(arr, ARR_LENGTH);
    }
    return 0;
}

问题原因 #

merge函数中，当左子数组left_arr还有剩余元素未拷贝回原数组时，没有处理这部分元素。原代码只处理了右子数组right_arr的剩余元素，导致原数组中对应位置保留了之前的旧值，从而出现重复元素和缺失元素。

修复方案 #

在merge函数的最后，添加处理左子数组剩余元素的循环：

void merge(int *arr, int left, int mid, int right){
    int length1 = mid - left + 1;
    int length2 = right - mid;
    int left_arr[length1];
    int right_arr[length2];

    int i, j;
    for (i=0; i<length1; i++)
        left_arr[i] = arr[left+i];
    for (j=0; j<length2; j++)
         right_arr[j] = arr[mid + 1 + j];

    i=0;
    j=0;
    int k = left;
    while(i<length1 && j<length2){
        if (left_arr[i]<=right_arr[j]){ 
            arr[k] = left_arr[i]; 
            i++;
        }
        else{
            arr[k] = right_arr[j]; 
            j++;
        }
        k++;
    }
    // 新增：处理左子数组剩余元素
    while (i<length1){
        arr[k] = left_arr[i];
        i++;
        k++;
    }
    while (j<length2){
        arr[k] = right_arr[j];
        j++;
        k++;
    }
}

额外优化建议 #

主函数中使用strtod（转换为double类型）给int数组赋值，可能会有精度问题，建议改用strtol或atoi来转换字符串为整数：

arr[i-1] = atoi(argv[i]);
// 或者更安全的strtol写法
arr[i-1] = strtol(argv[i], NULL, 10);

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