C – 合并合并排序的一部分

我是新来合并排序，我正在尝试创建一个。 我的合并排序不是排序我发送它的数组，我无法弄清楚为什么。 这里是所有代码http://pastebin.com/M4RUzhUa的链接

这是我的mergesort函数

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

这是我的（更新的）合并function

 void merge(int array[], int low, int middle, int high) { int size,left,right,i, j; size = high - low + 1; int array1[high]; left = low; right = middle + 1; i = low; while ((left<=middle) && (right<=high)) { if(array[left] < array[right]) { array1[i] = array[left]; left++; i++; } else { array1[i] = array[right]; right++; i++; } } while (left <= middle) { array1[i] = array[left]; left++; i++; } while (right <= high) { array1[i] = array[right]; right++; i++; } for (j = low; j < i; j++) { array[j] = array1[j]; } } 

在我的程序中，输入数组是

9 3 2 1 5

而输出是

0 1 2 3 5

第一个我想不通的元素正在发生一些事情

Answer 1

更新代码的新评论：

看起来你正在跳过数组的末尾。 测试的方法是在数组周围添加一些保护变量，如下所示：

 #define NUM_OF_INTS 5 #define DEBUG 1 int main() { int frontguard=-500; int numbers[NUM_OF_INTS]; int backguard=-600; int i; srand(0); //Fill the array for( i = 0; i < NUM_OF_INTS; i++ ) { //Use random numbers //numbers[i] = rand()%10000; //Use reverse sorted list numbers[i] = NUM_OF_INTS-i; //Use sorted list //numbers[i] = i; } if (DEBUG == 1) printf( "Unsorted list\n" ); if (DEBUG == 1) printarray( numbers, 0, NUM_OF_INTS/2, NUM_OF_INTS ); if (DEBUG == 1) printf( "frontguard=%04d, backguard=%04d\n", frontguard, backguard); merge_sort( numbers, 0, NUM_OF_INTS ); if (DEBUG == 1 ) printf( "\nSorted list\n"); if (DEBUG == 1) printarray( numbers, 0, NUM_OF_INTS/2, NUM_OF_INTS ); if (DEBUG == 1) printf( "frontguard=%04d, backguard=%04d\n", frontguard, backguard); return 0; } 

printarray是我写的一个帮助函数，用于绘制数组中正在发生的事情

 void printarray( const int arr[], const int low, const int middle, const int high ) { int i; for (i = low; i < high; i++ ) { if( i == low ) printf( " L%04d", i ); else if( i == middle ) printf( " M%04d", i ); else if( i == (high-1) ) printf( " H%04d", i ); else printf( " *%04d", i ); } printf( "\n" ); for( i = low; i < high; i++ ) printf( " %04d", arr[i] ); printf( "\n" ); } 

如果你没有/想要一个调试器，通常需要创建一些辅助调试function，以使代码正常工作。 不要害怕写一些丢失的代码来理解你的代码在做什么！ 在这种情况下，我不需要L / M / H线，但仍然值得花时间。 我建议将这些类型的函数留在代码中，注释掉（使用#define，如DEBUG），以防将来的维护者需要它们。

以下是您的函数输出：

 Unsorted list L0000 *0001 M0002 *0003 H0004 0005 0004 0003 0002 0001 frontguard=-500, backguard=-600 Sorted list L0000 *0001 M0002 *0003 H0004 -600 0001 0002 0003 0004 frontguard=-500, backguard=0005 

您可以看到backguard被覆盖并“被盗”到您的输出中。 （这种行为在不同的CPU体系结构，C实现和运行细节上可能有所不同，顺便说一句。）问题是你从main()调用merge_sort ，并且调用数组的大小（在本例中为5），但merge_sort期望high成为数组中的最后一个有效索引（数字[4]是最后一个数组项）。 将main()修改为

  merge_sort( numbers, 0, NUM_OF_INTS-1 ); 

并根据已排序，反向排序和随机的数字数组对其进行测试。

---

原评论：

好吧，首先，您应该收到一个分段错误，而不仅仅是错误排序的数据。

  size = high - low + 1; //create a helper array and set it equal to the input array int array1[size]; for (i = low; i <= high; i++) { array1[i] = array[i]; } 

想想当low不为零时，这里会发生什么。 假设l = 6，m = 6，h = 7。 您正在将辅助数组的大小设置为2，但是您正在使用i = 6访问它，因此您正在废弃堆栈。

最简单的解决方法是声明int array1[high]; 。 它的内存效率低，但它使代码的其余部分保持简单，这确实更有价值。

其次，你的for循环索引超过数组的结尾，你需要使用i

  for (i = low; i < high; i++) { 

这些将修复您的分段错误。 修复后，您仍然在输出中获取垃圾数据。

您的中间else-if语句永远不会被执行 - 任何等效数据将由第一个if语句覆盖。

你的while循环不能正确处理退化情况。 它需要检测两个列表中的一个是否已被完全消耗，如果是，则只需复制其他列表的其余部分。

此外，while循环需要单独的跟踪变量用于低，中和输出数组。 您不能将currentLow用于低数组和输出数组。

最后，在测试排序时，随机数据是不够的（特别是大小为5），您应该始终测试排序和反向排序列表的完全退化情况。