为什么这个合并排序不起作用？它给出相同的未排序数组

Question

我编写了这段代码来实现合并排序，它从用户处获取输入数组并使用合并排序对该数组进行排序。但它会给出与输入相同的输出。

我还将临时数组 ( temp[]) 复制到array[].

请检查我的代码并给我解决方案，谢谢。

#include <stdio.h>

void merge(int array[], int mid, int low, int high) {
    int i, j, k, temp[100];
    
    i = low;
    k = low;
    j = mid + 1; 
    
    while (i <= mid && j <= high) {
        if (array[i] < array[j]) {
            temp[k] = array[i];
            i++;
            k++;
        } else {
            temp[k] = array[j];
            j++;
            k++;
        }
    }
    
    while (i <= mid) {
        temp[k] = array[i];
        i++;
        k++;
    }
    
    while (j <= high) {
        temp[k] = array[j];
        j++;
        k++;
    }
    
    for (int i = low; i <= high; i++) {
        array[i] = temp[i];
    }
}

void mergeSort(int array[], int low, int high) {
    int mid;
    if (low < high) {
        mid = (low + mid) / 2;
        mergeSort(array, low, mid);
        mergeSort(array, mid + 1, high);
        merge(array, mid, low, high);
    }
}

void printArray(int *array, int n) {
    for (int i = 0; i < n; i++) {
        printf("%d  ", array[i]);
    }
    printf("\n");
}

void main() {
    int array[100], n, target, p;
   
    printf("How many number you want to insert?\n");
    scanf("%d", &n);
   
    // printf("Target: ");
    // scanf("%d", &target);
   
    for (p = 0; p < n; p++) {
        scanf("%d", &array[p]);
    } 
    
    printArray(array, n);
    mergeSort(array, 0, n);
    printArray(array, n);
}

这是我的输出

输出：

#include <stdio.h>

void merge(int array[], int mid, int low, int high) {
    int i, j, k, temp[100];
    
    i = low;
    k = low;
    j = mid + 1; 
    
    while (i <= mid && j <= high) {
        if (array[i] < array[j]) {
            temp[k] = array[i];
            i++;
            k++;
        } else {
            temp[k] = array[j];
            j++;
            k++;
        }
    }
    
    while (i <= mid) {
        temp[k] = array[i];
        i++;
        k++;
    }
    
    while (j <= high) {
        temp[k] = array[j];
        j++;
        k++;
    }
    
    for (int i = low; i <= high; i++) {
        array[i] = temp[i];
    }
}

void mergeSort(int array[], int low, int high) {
    int mid;
    if (low < high) {
        mid = (low + mid) / 2;
        mergeSort(array, low, mid);
        mergeSort(array, mid + 1, high);
        merge(array, mid, low, high);
    }
}

void printArray(int *array, int n) {
    for (int i = 0; i < n; i++) {
        printf("%d  ", array[i]);
    }
    printf("\n");
}

void main() {
    int array[100], n, target, p;
   
    printf("How many number you want to insert?\n");
    scanf("%d", &n);
   
    // printf("Target: ");
    // scanf("%d", &target);
   
    for (p = 0; p < n; p++) {
        scanf("%d", &array[p]);
    } 
    
    printArray(array, n);
    mergeSort(array, 0, n);
    printArray(array, n);
}

Answer 1

有两个错误。第一个是在mergeSort：

mid = (low + mid)/2;

它尝试mid根据自身进行定义，但它仍然是一个未定义的值。将其更改为：

mid = (low + high)/2;

第二个错误是在main对 的调用中mergeSort：

mergeSort(array, 0, n);

这是一个相差一的错误，因为mergeSort包含下限和上限。将其更改为：

mergeSort(array, 0, n-1);

通过这两个修复，代码可以按预期工作：

How many number you want to insert?
4
6
4
7
5
6  4  7  5  
4  5  6  7