c - 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)添加 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);
}