合并排序算法建议

Question

我做了一个程序，使用合并排序算法对列表进行排序。

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

感谢

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 

Answer 1

您是按值传递的指针，因此该值分配给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越界（对于给定示例）。

Answer 2

我想有很多错误，在此代码，但最大的一个是

niz = niz2; 

在这里，您正试图将niz2阵列复制回niz，但它没有做到这一点，它只是拷贝指针。

Answer 3

我看到您试图通过niz = niz2; 将niz2的内容分配到niz。这是不正确的，因为niz是一个按值传递的指针，而niz2是一个指向数组的本地指针。

如果要复制niz2到niz您可能需要像for (int i = low; i < high; i++) niz[i] = niz2[i]一个循环，使用API​​函数类似的memcpy覆盖输入阵列，或者如果你想在int* niz指针使用新创建的niz2阵列重定向，那么你需要通过输入作为指针指针，然后直接修改它，例如merge_sort(int** niz, int low...)并通过merge_sort(&niz, 0, 20);调用它。这并不是说，如果你做的修改输入指针指向一个新的数组，你应该删除旧的第一，如delete [] *niz; *niz = niz2;

声明niz = niz2;复制地址指向niz2了在参数列表中的临时niz指针。当您将指针传递给接收int*（如foo(int* nPtr);）的函数时，您发送的指针将被复制到临时变量/指针nPtr中。使用foo(int** nPtr);告诉它它正在处理'int指针的地址'，而不仅仅是'int的地址'。在这种情况下，您可以通过*nPtr = &tmpInt或*nPtr = tmpPtr等语句重定向nPtr。要从源头获得实际的int或数据，您可以使用tmpInt = **nPtr。