谁能解释为什么我的合并排序不起作用？

Question

任何人都可以解释为什么这不起作用吗？我无法对数组中的数字进行排序并将其放入空 b 数组中。我到处搜索，但似乎有什么东西让我望而却步，我的 cod3rz 同胞!

#include <stdio.h>
#include <string.h>

void merge(int array[], int low, int mid, int high);
void midpoint(int array[], int low, int high);

int main(int argc, const char * argv[]){

    int b[100];

    int array[] = { 13, 23, 37, 45, 55, 68, 79, 93};
    int arrayLength = sizeof(array)/sizeof(array[0]);


    for (int i =0 ; i < arrayLength; i++){
        for ( int j= 1 + i ; j < arrayLength; j++){

            midpoint(&array[i], i ,j );{

            }
        printf("%d\n", *b);
        }
    }

    return 0;
}


void merge(int array[], int low, int mid, int high)
{
    int b[100];
    int b[100];
    int i = low;
    int b[100];
    int j = mid + 1;
    int b[100];
    int k = 0;

    while (i <= mid && j <= high) {
        if (array[i] <= array[j])
            b[k++] = array[i++];
        else
            b[k++] = array[j++];
    }
    while (i <= mid)
        b[k++] = array[i++];

    while (j <= high)
        b[k++] = array[j++];

    k--;
    while (k > 0) {
        array[low + k] = b[k];
        k --;
    }

}

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

}

Answer 1

首先，您没有将 b 数组传递给递归调用，因此无法填充它。此外，您应该能够在协助合并操作的助手数组的帮助下，在 array 中就地进行排序。因此，在顶层不需要 b。

您的 merge() 函数有点相反。你应该做的是首先将整个 array 数组复制到临时 b 数组中，然后从 b 合并到 array.

这样，当算法完成时，array 将在顶层排序，然后您就有了排序后的数组。

此外，删除嵌套的 for 循环。由于 MergeSort 是一种递归分而治之算法，您应该只调用一次 midpoint()，如果正确实现，递归将处理其余部分。

所以这样:

 for (int i =0 ; i < arrayLength; i++){
        for ( int j= 1 + i ; j < arrayLength; j++){

            midpoint(&array[i], i ,j );{

        }
        printf("%d\n", *b);
    }

应该是这样的:

 midpoint(array, 0 ,arrayLength-1 );

另外，你有一个括号问题，从这一行中取出左括号，并根据需要清理右括号:

中点(&array[i], i ,j );{

编辑:除了我上面列出的内容之外，实际上还有很多问题。我不太愿意用勺子喂你答案，因为这可能是一项学校作业，但由于你付出了很大的努力并且你的一般代码结构几乎是正确的，而且你并不是不能在线搜索和找到类似的解决方案，我会继续发布这个。

这是一个基于您的代码正确实现 MergeSort 算法的有效解决方案:

#include <stdio.h>
#include <string.h>

void merge(int *array, int low, int mid, int high);
void midpoint(int *array, int low, int high);

int main(int argc, const char * argv[]){

    int array[] = { 100, 13, 44, 23, 22, 37, 3, 45, 2, 55, 68, 1, 79, 93, 4};
    int arrayLength = sizeof(array)/sizeof(array[0]);

    //start the recursive calls
    midpoint(array, 0 ,arrayLength-1 );

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

    return 0;
}


void merge(int *array, int low, int mid, int high)
{
    int b[100];

    //copy the current elements into temp array
    int v;
    for (v = low; v <= high; v++){
        b[v] = array[v];
    }

    int i = low;
    int j = mid + 1;
    int k = low;

    //merge left side and right side into array in sorted order
    while (i <= mid && j <= high) {
        if (b[i] <= b[j])
            array[k++] = b[i++];
        else
            array[k++] = b[j++];
    }

    //The left side might have left-over elements
    while (i <= mid)
        array[k++] = b[i++];


}

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

}

输出:

1
2
3
4
13
22
23
37
44
45
55
68
79
93
100