2

我制作了一个使用合并排序算法对列表进行排序的程序。

问题是我认为它应该工作但它不工作，合并函数返回一个作为参数发送的数组。你能不能看看我写的代码，告诉我哪里出了问题，以及如何改进它。

谢谢

void merge_sort(int *niz, int low, int medium, int high) {

int *niz2 = new int[high-low];

int bottom = low;
int top = medium + 1;

for (int f1=low; f1<high-low; f1++) {
    if (low > medium) {
        niz2[f1] = niz[top++];
    }
    else if (top > high) {
        niz2[f1] = niz[bottom++];
    }
    else if (niz[bottom] < niz[top]) {
        niz2[f1] = niz[bottom++];
    }
    else {
        niz2[f1] = niz[top++];
    }
}
niz = niz2;
}

void merge(int *niz, int low, int high) {
if (low < high) {
    int medium = (high+low)/2;
    merge(niz, low, medium);
    merge(niz, medium+1, high);
    merge_sort(niz, low, medium, high);        
}
}

程序的输出：

3 5 2 3 4 9 5 2 7 10 
3 5 2 3 4 9 5 2 7 10
4

3 回答 3

4

您正在按值传递指针，因此您分配给niz内部函数的值在调用者函数中不可见。

您的签名应该是 void merge(int niz[], int low, int medium, int high)和 void merge_sort(int niz[], int low, int high)。

您在底部merge命名merge_sort了 ，那么您应该将内容从 复制回niz2，niz而不是niz = niz2。

*编辑 - * 你也得到了merge错误的功能（你已经命名merge_sort）。如果说你用low = 100, medium = 120,调用函数high = 140。

然后for (int f1=low; f1<high-low; f1++)永远不会循环。

应该是for (int f1=0; f1<high-low; f1++)。上述错误的另一个后果是SIGSGV，因为您将访问，niz2超出范围（对于给定的示例）。

于 2012-09-15T07:31:26.410 回答
3

我认为这段代码有很多错误，但最大的错误是

niz = niz2;

在这里，您试图将niz2数组复制回niz，但它没有这样做，它只是复制指针。

于 2012-09-15T07:36:39.543 回答
1

我看到您正在尝试将内容分配niz2给nizvia niz = niz2; 。这是不正确的，因为niz它是按值传递的指针，并且niz2是指向数组的本地指针。

如果你想复制niz2给niz你，要么需要一个循环for (int i = low; i < high; i++) niz[i] = niz2[i]，使用像 memcpy 这样的 api 函数来覆盖输入数组，或者如果你试图重定向int* niz指针以使用新创建的niz2数组，那么你需要将输入传递为一个指向指针的指针然后直接修改它，例如merge_sort(int** niz, int low...)并通过merge_sort(&niz, 0, 20);. 并不是说如果你修改输入指针指向一个新数组，你应该先删除旧的，例如delete [] *niz; *niz = niz2;

该语句通过参数列表中的临时指针niz = niz2;复制指向的地址。当您将指针传递给接收（例如）的函数时，您发送的指针将被复制到临时变量/指针中。Using告诉它它正在使用“指向和 int 的指针的地址”，而不仅仅是“int 的地址”。在这种情况下，您可以通过类似or的语句进行重定向。要从源头获取实际数据或数据，您可以使用.niz2nizint*foo(int* nPtr);nPtrfoo(int** nPtr);nPtr*nPtr = &tmpInt*nPtr = tmpPtrinttmpInt = **nPtr

于 2012-09-15T07:37:34.583 回答