$gcc -Wall -g merge_sort.c
我有一个问题,因为数字：
2 4 5 7 1 2 3 6
结果是：
1 2 2 3 3 4 5 5
我试图仔细阅读伪代码,但这并不能帮助我.
我想知道我在做错什么以下是我的代码：
#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 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,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,SIZE);
print_array(dataset,SIZE);
return 0;
}
编辑：(正确解决方案)
void merge(int * array_of_integers,int r){
int n1 = q - p + 1;
int n2 = r - q;
int i,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 r){
if(p < r){
int q = (p+r)/2;
merge_sort(array_of_integers,q);
merge_sort(array_of_integers,r);
merge(array_of_integers,r);
}
}
解决方法
一个,你需要弄清楚你所传递的参数是什么意思.在merge_sort中,看起来p是要排序的第一个元素,r是要排序的最后一个元素.但是,在调用merge_sort时,在main中,它被传递为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的循环,对于(k = p; k
相关文章
- 预期的反转数 - 从Cormen的算法介绍
- Wand 算法介绍与实现
- 数组 - 如何使用合并排序算法就地排序？
- 如何在现代C中实现经典排序算法？
- 算法 - 为什么合并排序比快速排序更喜欢排序链表
- 算法 - 搜索引擎如何从倒排索引中合并结果？
- 如何在c中实现自然排序算法？
- 算法 - 非递归合并排序
转载注明原文：如何从Cormen和Co的“算法介绍”中实现合并排序 - 代码日志