我正在从Cormen and Co.学习算法，并且在从其伪代码实现合并排序方面遇到问题.我是通过以下方式编译的:
I'm learning algorithms from Cormen and Co. and I have problem with implementation of merge sort from their pseudocode. I compiled it by:
$ gcc -Wall -g merge_sort.c我有一个问题，因为数字:
I have a problem because for numbers:
2 4 5 7 1 2 3 6结果是:
1 2 2 3 3 4 5 5我试图仔细阅读伪代码，但这对我没有帮助. 我想知道我在做什么错.下面是我的代码:
I tried to read carefully the pseudo code but this does not help me. I want to know what I'm doing wrong. Below is my code:
#include <stdio.h> #define SIZE 8 void merge(int *array_of_integers, int p, int q, int r) { int n1 = q - p + 1; int n2 = r - q; int i, j, k; int left_array[n1 + 1]; int right_array[n2 + 1]; for (i = 0; i < n1; i++) left_array[i] = array_of_integers[p + i]; for (j = 0; j < n2; j++) right_array[j] = array_of_integers[q + j]; i = 0; j = 0; for (k = p; k < r; k++){ if (left_array[i] <= right_array[j]) { array_of_integers[k] = left_array[i]; i++; } else { array_of_integers[k] = right_array[j]; j++; } } } void merge_sort(int *array_of_integers, int p, int r) { if (p < r) { int q = (p + r) / 2; merge_sort(array_of_integers, p, q); merge_sort(array_of_integers, q + 1, r); merge(array_of_integers, p, q, r); } } void print_array(int *array_of_integers, int amout_of_integers) { int i; for(i = 0; i < amout_of_integers; i++) printf("%d ", array_of_integers[i]); puts(""); } int main(void) { int dataset[] = { 2, 4, 5, 7, 1, 2, 3, 6 }; print_array(dataset, SIZE); merge_sort(dataset, 0, SIZE); print_array(dataset, SIZE); return 0; }(正确的解决方案)
void merge(int *array_of_integers, int p, int q, int r) { int n1 = q - p + 1; int n2 = r - q; int i, j, k; int left_array[n1 + 1]; int right_array[n2 + 1]; left_array[n1] = 123456798; right_array[n2] = 123456798; for (i = 0; i < n1; i++) left_array[i] = array_of_integers[p + i]; for (j = 0; j < n2; j++) right_array[j] = array_of_integers[q + j + 1]; i = 0; j = 0; for (k = p; k <= r; k++) { if (left_array[i] <= right_array[j]) { array_of_integers[k] = left_array[i]; i++; } else { array_of_integers[k] = right_array[j]; j++; } } } void merge_sort(int *array_of_integers, int p, int r) { if(p < r) { int q = (p + r) / 2; merge_sort(array_of_integers, p, q); merge_sort(array_of_integers, q + 1, r); merge(array_of_integers, p, q, r); } }推荐答案
您的代码中有两个问题.
There are two problems in your code.
首先，您需要弄清楚所传递的参数的含义.在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为零时，这将复制第一个范围的最后一个元素，但是您需要第二个范围的第一个元素.因此，您需要清除索引的这些用途. (此外，left_array和right_array只需要n1和n2个元素，而不是n1 + 1和n2 + 1.)还要检查k上的循环for(k = p; k < r; k++).该循环的延续条件应该是什么?
One, you need to clarify what the parameters you are passing mean. Inside merge_sort, it looks like p is the first element to be sorted, and r is the last element to be sorted. But, where merge_sort is called, in main, it is passed 0 and SIZE. Here, 0 is the first element to be sorted, but SIZE cannot be the last element, because it is (presumably) the number of elements to be sorted. In your example, you are passing 8, but the last element to be sorted is 7. So decide whether you want to change merge_sort so that r is the number of elements or whether you want to change main to pass SIZE-1. Similarly, in merge, p seems to be the first element to merge, q is the last element of the first range (so q+1 is the first of the second), and r is the last element of the second range. But when you copy from array_of_integers to right_array, you copy from q+j. When j is zero, this copies the last element of the first range, but you want the first element of the second range. So you need to clear up these uses of the indices. (Also, you only need n1 and n2 elements for left_array and right_array, not n1+1 and n2+1.) Also check the loop on k, for(k = p; k < r; k++). What should the continuation condition on that loop be?
二，当合并left_array和right_array时，您不会考虑数组可能为空的事实(因为以前所有元素都已从数组中复制出来)，因此将left_array [i]与right_array [j]进行比较不起作用，因为i或j分别指示left_array或right_array之外的元素.例如，如果我已达到其限制(n1)，则不应进行比较.相反，您应该只从right_array中获取一个元素.
Two, when you merge left_array and right_array, you do not account for the fact that an array might be empty (because all elements have been copied out of it previously), so comparing left_array[i] to right_array[j] does not work because i or j is indicating an element outside of the left_array or of the right_array, respectively. For example, if i has reached its limit (n1), then you should not compare. Instead, you should just take an element from right_array.