C 中的合并排序给出错误的结果

Question

我写了一个归并排序程序，但我得到了错误的结果。

我见过其他类似的程序，但它们没有帮助我解决问题。我认为问题出在 merge 函数中。

#include <stdio.h>
#include "stdafx.h"           

#define Size 5

//this is the array
int arr[Size] = { 5, 4, 3, 2, 1 };
int sr[10];
void mergesort(int a[], int start, int end, int size);
void merge(int a[], int start, int end, int size);

int main(void) {
    mergesort(arr, 0, 4, 5);
    for (int i = 0; i < Size; i++) {
        printf_s("%i", sr[i]);
    }
    printf_s("\n");
    return 0;        
}

void mergesort(int a[], int start, int end, int size) {
    if (size < 2)
        return;

    int s = size / 2;
    mergesort(a, start, (start + end) / 2, s);
    mergesort(a, (start + end) / 2, end, s);
    merge( a,  start,  end,  s);
}

void merge(int a[], int start, int end, int size) {
    int left = start;
    int right = ((start + end) / 2) + 1;

    for (int i = 0; i < size; i++) {
        if (left < (start + end)/2) {
            if (right >= end) {
                sr[i] = arr[left];
                left++;
            } else
            if (arr[left] < arr[right]) {
                sr[i] = arr[left];
                left++;
            } else {
                sr[i] = arr[right];
                right++;
            }
        } else {
            sr[i] = arr[right];
            right++;
        }
    }
}

Answer 1

(1) printf_s("%i",sr[i]); 应该是 printf_s("%i ", arr[i]);

(2)

mergesort(a, start, (start + end) / 2, s);//E.g index:{0,1,2,3,4}, start:0, (start + end) / 2 : 2, s: 2, but 0(start),1,2(new end), this length is 3, not 2
mergesort(a, (start + end) / 2, end, s);//Duplicate start position and length should be size - s. E.g size:5, s:2, rest size is 3, not 2.
merge( a,  start,  end,  s);//s should be size

应该是

mergesort(a, start, start + s - 1, s);
mergesort(a, start + s, end, size - s);
merge(a, start, end, size);

(3) 按(2)
改将 int right = ((start + end) / 2) +1; 更改为 int right = start + size / 2;。

(4) Add int sr[size]; //避免使用全局变量。最好使用 malloc。例如 int *sr = malloc(size*sizeof(int));...free(sr);

(5)

if (left < (start+end)/2)
{
    if (right >= end)

应该是

if (left < start + size / 2)
{
    if (right > end){//Should be >, not >=

(6) 写回 arr 表格 sr 是必要的

完整代码：

#include <stdio.h>
#include <stdlib.h>

void mergesort(int a[], int start, int end, int size);
void merge(int a[], int start, int end, int size);

int main(void){
    int arr[] = {5,4,3,2,1};
    int size = sizeof(arr)/sizeof(*arr);

    mergesort(arr, 0, size - 1, size);
    for (int i = 0; i < size; i++){
        printf_s("%i ", arr[i]);
    }
    printf_s("\n");
    return 0;
}

void mergesort(int a[], int start, int end, int size){
    if (size < 2)
        return;

    int s = size / 2;
    mergesort(a, start, start + s - 1, s);
    mergesort(a, start + s, end, size - s);
    merge(a, start, end, size);
}
void merge(int a[], int start, int end, int size){
    int left = start;
    int right = start + size / 2;
    int right_start = right;

    int *sr = (int*)malloc(size*sizeof(*sr));//Cast(int*) is not necessary in C.

    for (int i = 0; i < size; i++){
        if (left < right_start){
            if (right > end){
               sr[i] = a[left++];
            } else if (a[left] < a[right]) {
                sr[i] = a[left++];
            } else {
                sr[i] = a[right++];
            }
        } else {
            sr[i] = a[right++];
        }
    }
    for(int i = 0; i < size; ++i)//write back.
        a[start + i] = sr[i];
    free(sr);
}

Answer 2

您的代码无效有多种原因：

mergesort 将范围分成大小 size / 2 的两半，如果 size 不是偶数，这是不正确的。
mergesort的参数不正确，只需要指针和大小。
merge 函数从全局数组 arr 而不是参数数组中获取值，并将值存储到全局临时数组 sr 中，但不将其复制回 a 数组。

这是更正和简化的版本：

#include <stdio.h>

void mergesort(int a[], int size);

int main(void) {
    int arr[] = { 5, 4, 3, 2, 1 };
    int size = sizeof(arr) / sizeof(arr[0]);

    mergesort(arr, size);
    for (int i = 0; i < size; i++) {
        printf_s("%i ", arr[i]);
    }
    printf_s("\n");
    return 0;        
}

void merge(int a[], int mid, int size) {
    int sr[mid];  // temporary array for the left part

    if (a[mid - 1] <= a[mid]) { // quick check for sorted case
        return;
    }
    for (int i = 0; i < mid; i++) {  // save left part
        sr[i] = a[i];
    }
    // merge into array `a`.    
    for (int i = 0, left = 0, right = mid; left < mid; i++) {
        if (right == size || sr[left] <= a[right]) {
            a[i] = sr[left++];
        } else {
            a[i] = a[right++];
        }
    }
}

void mergesort(int a[], int size) {
    if (size >= 2) {
        int mid = (size + 1) / 2; // make left part no smaller than right part
        mergesort(a, mid);
        mergesort(a + mid, size - mid);
        merge(a, mid, size);
    }
}

C 中的合并排序给出错误的结果

Merge sort in C giving wrong results

c

mergesort