通过修改c中的合并排序对数组的偶数索引进行排序

Question

我有一个问题，我们需要使用分治法仅对数组的偶数索引进行排序。

我尝试的是修改原始的

mergeSort

函数，以便它对子数组的偶数元素进行排序。但在合并排序函数中，我们不会得到每个元素，因为如果得到一个元素，我们就不知道该放在哪里，因此我这样做的目的是使子数组大小为 3 或 4 时为基本情况。它将对子数组进行排序，但仅对主数组的偶数索引中的偶数索引进行排序，因此第 x 行。 我得到的结果是奇数元素没有受到影响，但偶数元素没有正确排序。 下面是我的代码：

#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;
    }
}

Answer 1

代码中存在多个问题：

• 循环

  for (int i = 0; i < n1; i = i + 2) { arr[i] = arr1[i]; }

  是不正确的，因为你应该使用

  arr[l + i]

  而不是

  arr[i]

  ，但即使更正，它仍然是无用的：只需忽略偶数索引处的元素即可。
• 另请注意，递归调用中的偶数索引不一定是原始数组中的偶数索引，因为您计算

  int mid = si + (ei - si) / 2;

  可能会产生奇数值。
• 您制作了长度为 3 和 4 的切片的特殊情况，但问题在于用奇数左切片长度分割数组。
• 使用包含上限的约定会导致复杂的代码，并且容易出错

  +1

  /

  -1

  调整。在 C 中使用排除的上限更简单。

这是修改后的版本：

#include <stdio.h>

void merge(int arr[], int lo, int mid, int hi); // hi is excluded
void mergeSort(int arr[], int lo, int hi);  // hi is excluded

int main(void) {
    int num;
    
    if (scanf("%d", &num) != 1 || num <= 0)
        return 1;
    int arr[num];
    for (int i = 0; i < num; i++) {
        if (scanf("%d", &arr[i]) != 1)
            return 1;
    }
    
    mergeSort(arr, 0, num);
    
    for (int i = 0; i < num; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

void mergeSort(int arr[], int lo, int hi) {
    if (hi - lo > 2) {
        /* split the array balanced halves with an even length for the left slice */
        int mid = lo + (hi - lo + 1) / 4 * 2;
        mergeSort(arr, lo, mid);
        mergeSort(arr, mid, hi);
        merge(arr, lo, mid, hi);
    }
}

void merge(int arr[], int lo, int mid, int hi) {
    int i, j, k;
    int n1 = (mid - lo) / 2;
    int arr1[n1];
 
    // save the elements at even index values in the left slice
    for (i = 0, j = lo; i < n1; i++, j += 2) {
        arr1[i] = arr[j];
    }

    // merge the slices, using only elements at even index values
    for (i = 0, j = mid, k = lo; i < n1 && j < hi; k += 2) {
        if (arr1[i] <= arr[j]) {
            arr[k] = arr1[i];
            i += 1;
        } else {
            arr[k] = arr[j];
            j += 2;
        }
    }
    // copy remaining elements from left slice
    while (i < n1) {
        arr[k] = arr1[i];
        k += 2;
        i += 1;
    }
    // remaining elements from right slice are already in their final places
}

输出：

chqrlie$ ./230902-sorteven
11
7 1 3 24 34 53 2 56 7 7 8
2 1 3 24 7 53 7 56 8 7 34