基于分治法修改归并排序实现数组偶数索引元素排序的问题排查

我想用分治法只对数组的偶数索引元素排序，于是修改了归并排序函数，设置了子数组长度为3或4的基准情况，只针对原数组的偶数索引元素处理（对应代码里的x行）。现在奇数索引元素确实没被改动，但偶数索引的排序结果不对，附上我的C语言代码，求帮忙排查问题。

#include <stdio.h>

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

int main() {
    int num;
    
    scanf("%d", &num);
    int arr[num];
    for (int i = 0; i < num; i++) {
        scanf("%d", &arr[i]);
    }
    
    mergeSort(arr, 0, num - 1);
    
    for (int i = 0; i < num; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

void mergeSort(int arr[], int si, int ei) {
    if ((ei - si == 2) && (si % 2 == 0)) {
        if (arr[si] > arr[si + 2]) {
            int temp = arr[si];
            arr[si] = arr[si + 2];
            arr[si + 2] = arr[si];
        }
    }                                     //base case 1
    
    if ((ei - si == 3)) {
        int x = (si % 2 == 0) ? si : si + 1;      //line x
        if (arr[x] > arr[x + 2]) {
            int temp = arr[x];
            arr[x] = arr[x + 2];
            arr[x + 2] = arr[x];
        }                                 //base case 2
    }
    if (si < ei) {
        int mid = si + (ei - si) / 2;
        mergeSort(arr, si, mid);             //calling merge sort on both the halves of array
        mergeSort(arr, mid + 1, ei);
        
        merge(arr, si, mid, ei);
    }
}

void merge(int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;
 
    int arr1[n1], arr2[n2];
 
    for (i = 0; i < n1; i++)
        arr1[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        arr2[j] = arr[m + 1 + j];
    
    for (int i = 0; i < n1; i = i + 2) {
        arr[i] = arr1[i];
    }
    i = (n1 % 2 == 0) ? 0 : 1;
    for (;i < n2; i = i + 2) {
        arr[i+n1] = arr2[i];
    }
    
    i = 0;
    j = (n1 % 2 == 0) ? 0 : 1, k = l;
    
    while (i < n1) {
        arr[k] = arr1[i];
        k = k + 2;
        i = i + 2;
    }
    
    while (j < n2) {
        arr[k++] = arr2[j];
        k = k + 2;
        j = j + 2;
    }
    
    while (i < n1) {
        arr[k] = arr1[i];
        k = k + 2;
        i = i + 2;
    }
    
    while (j < n2) {
        arr[k] = arr2[j];
        k = k + 2;
        j = j + 2;
    }
}

问题排查与修复 #

1. 基准情况的交换错误

两个基准情况里的元素交换逻辑都写错了：

// 错误写法
arr[si + 2] = arr[si];
// 正确写法
arr[si + 2] = temp;

第二个基准情况的交换也犯了同样的错误，这会导致交换后两个位置的元素完全相同，根本无法完成排序。

2. 基准情况逻辑冗余且片面

当前的基准条件只覆盖了长度3（ei-si=2）和4（ei-si=3）的子数组，且会和后面si < ei的递归逻辑重复执行，导致多次不必要的无效处理。合理的基准情况应该是：当子区间内的偶数索引元素数量≤1时，直接返回，无需处理。

3. Merge函数逻辑完全错误

当前的merge函数没有实现归并排序的核心——将两个有序子数组合并为一个有序数组，只是在无意义地重复赋值。正确的merge应该只关注两个子区间里的偶数索引元素，将它们收集后排序，再放回原数组对应的偶数位置。

修复后的完整代码

#include <stdio.h>

// 仅合并两个子区间中的偶数索引元素
void mergeEvenIndices(int arr[], int start, int mid, int end) {
    // 统计左右两个区间的偶数索引元素数量
    int leftCount = ((mid - start) / 2) + 1;
    if (start % 2 != 0) leftCount--;
    
    int rightCount = ((end - (mid + 1)) / 2) + 1;
    if ((mid + 1) % 2 != 0) rightCount--;
    
    int left[leftCount], right[rightCount];
    int idx = 0;
    
    // 提取左区间的偶数索引元素
    for (int i = start; i <= mid; i += 2) {
        left[idx++] = arr[i];
    }
    
    idx = 0;
    // 提取右区间的偶数索引元素
    for (int i = mid + 1; i <= end; i += 2) {
        right[idx++] = arr[i];
    }
    
    // 合并两个有序数组到原数组的偶数索引位置
    int i = 0, j = 0;
    int k = (start % 2 == 0) ? start : start + 1;
    while (i < leftCount && j < rightCount) {
        if (left[i] <= right[j]) {
            arr[k] = left[i++];
        } else {
            arr[k] = right[j++];
        }
        k += 2;
    }
    
    // 处理剩余元素
    while (i < leftCount) {
        arr[k] = left[i++];
        k += 2;
    }
    while (j < rightCount) {
        arr[k] = right[j++];
        k += 2;
    }
}

// 仅对数组的偶数索引元素进行归并排序
void mergeSortEvenIndices(int arr[], int start, int end) {
    if (start >= end) return;
    
    int mid = start + (end - start) / 2;
    mergeSortEvenIndices(arr, start, mid);
    mergeSortEvenIndices(arr, mid + 1, end);
    
    mergeEvenIndices(arr, start, mid, end);
}

int main() {
    int num;
    scanf("%d", &num);
    int arr[num];
    
    for (int i = 0; i < num; i++) {
        scanf("%d", &arr[i]);
    }
    
    mergeSortEvenIndices(arr, 0, num - 1);
    
    for (int i = 0; i < num; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

代码说明

• mergeSortEvenIndices：递归划分区间，仅针对偶数索引元素执行归并排序逻辑
• mergeEvenIndices：提取左右子区间的偶数索引元素，合并为有序序列后放回原数组对应偶数位置
• 奇数索引元素全程未被修改，完全保留原始值

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