如何实现Cormen和Co的“算法导论”中的合并排序

如何实现Cormen和Co的“算法导论”中的合并排序

您的代码中有两个问题。

第一，您需要弄清楚所传递的参数的含义。在merge_sort内部，看起来p是要排序的第一个元素，r是要排序的最后一个元素。但是，在调用merge_sort的地方，主要是传递0和SIZE。这里，0是要排序的第一个元素，但SIZE不能是最后一个元素，因为（大概）它是要排序的元素数。在您的示例中，传递的是8，但是要排序的最后一个元素是7。因此，请决定是否要更改merge_sort，以使r为元素的数量，或者是否要更改main来传递SIZE-1。同样，在合并中，p似乎是要合并的第一个元素，q是第一个范围的最后一个元素（所以q
+ 1是第二个范围的第一个元素），r是第二个范围的最后一个元素。但是，当您从array_of_integers复制到right_array时，您从q +
j复制。当j为零时，这将复制第一个范围的最后一个元素，但是您需要第二个范围的第一个元素。因此，您需要清除索引的这些用途。（此外，您只需要n1和n2个元素用于left_array和right_array，而不需要n1
+ 1和n2 + 1。）还要检查k上的循环，

for(k = p; k < r; k++)

。该循环的延续条件应该是什么？

第二，合并left_array和right_array时，您不会考虑数组可能为空的事实（因为先前已将所有元素复制出该数组），因此将left_array
[i]与right_array
[j]进行比较不起作用，因为i或j分别指示left_array或right_array之外的元素。例如，如果我已达到其限制（n1），则不应进行比较。相反，您应该仅从right_array中获取一个元素。