合并排序实现不起作用
合并排序实现不起作用
提问于 2015-10-04 17:32:23
我试图使用数组在C中实现合并排序，下面是我的代码：
#include <stdio.h>
#include <stdlib.h>
void merge(int s[], int low, int middle, int high)
{
int i,l=0,r=0;
int left[high/2], right[high/2];
for(i = low; i<=middle; i++) left[i-low] = s[i];
for(i = middle+1; i<=high; i++) right[i-middle-1] = s[i];
i = low;
while(l <= middle-low || r <= high - middle - 1)
{
if(left[l] <= right[r])
{
s[i++] = left[l];
l++;
}
else
{
s[i++] = right[r];
r++;
}
}
while(l <= middle-low)
{
s[i++] = left[l];
l++;
}
while(r <= high - middle - 1)
{
s[i++] = left[r];
r++;
}
}
void mergesort(int s[], int low, int high)
{
int i;
int middle;
if(low < high){
middle = (low + high)/2;
mergesort(s, low, middle);
mergesort(s, middle+1, high);
merge(s, low, middle, high);
}
}
int main()
{
int nums[] = {5, 345, 1, 120, 40, 3450};
int size = (sizeof(nums))/(sizeof(int));
int i;
for(i = 0; i < size; i++)
printf("%d ", nums[i]);
printf("\n");
mergesort(nums, 0, size);
for(i = 0; i < size; i++)
printf("%d ", nums[i]);
printf("\n");
return 0;
}产出：
5 345 1 120 40 3450
0 1 4 5 40 120 有点接近了。有人能指出我的错误吗？谢谢。
回答 2
Stack Overflow用户
回答已采纳
发布于 2015-10-04 18:34:31
您可以在几个地方访问超出界限的数组。您的代码使用C样式的范围，它有一个包容的下限L和一个排他的上限H。排它意味着上限H不是(子)数组中的有效索引。范围内的典型循环如下所示：
for (i = L; i < U; i++) ...或
i = L;
while (i < U) ...在这样的循环中，一个大于或等于的操作符<=应该会让你感到警惕，而在某些情况下，它们可能是正确的，但它们通常是不一致数组索引的结果。
让我们用C样式范围来修改您的代码：
int left[high/2], right[high/2];数组大小是错误的。左数组有middle - low元素，右边数组有high - middle元素。如果数组大小high - low是奇数，则右侧比左侧多一个元素。
for(i = low; i<=middle; i++) left[i-low] = s[i];您错误地将中间元素放在左数组中。它是正确数组的第一个元素。
for(i = middle+1; i<=high; i++) right[i-middle-1] = s[i];这里也是一样，加上您访问的是数组之外的s[high]。
i = low;
while(l <= middle-low || r <= high - middle - 1)条件应该是<，而不是-1。更重要的是，条件应该都是真的，否则就会访问超出界限的子数组；因此操作符应该是&&`。
if(left[l] <= right[r])不过，<=一次也没问题。
while(l <= middle-low)
{
s[i++] = left[l];
l++;
}
while(r <= high - middle - 1)
{
s[i++] = left[r];
r++;
}在这里，应该又是<了。还请注意，您使用索引left访问r，这可能只是一个复制和粘贴错误。
if(low < high){
middle = (low + high)/2;
mergesort(s, low, middle);
mergesort(s, middle+1, high);
merge(s, low, middle, high);
}在这里，第二次呼叫巨石应该是middle，而不是middle + 1。由于上界是排他性的，而下界不是，所以相邻的数组共享相同的边界。
下面是一种行之有效的方法：
void merge(int s[], int low, int middle, int high)
{
int i, l = 0, r = 0;
int left[middle - low];
int right[high - middle];
for (i = low; i < middle; i++) left[i - low] = s[i];
for (i = middle; i < high; i++) right[i - middle] = s[i];
i = low;
while (low + l < middle && middle + r < high) {
if (left[l] < right[r]) {
s[i++] = left[l];
l++;
} else {
s[i++] = right[r];
r++;
}
}
while (low + l < middle) {
s[i++] = left[l];
l++;
}
while (middle + r < high) {
s[i++] = right[r];
r++;
}
}
void mergesort(int s[], int low, int high)
{
int middle;
if (low + 1 < high) {
middle = (low + high) / 2;
mergesort(s, low, middle);
mergesort(s, middle, high);
merge(s, low, middle, high);
}
}代码还可以改进。左、右子数组的不同索引使得维护和测试代码变得困难。如果您已经了解了指针算法，就可以完全通过将low和大小作为新数组基传递给array + low来完成，就像EOF在注释中所建议的那样。
Stack Overflow用户
发布于 2015-10-04 18:47:34
M·欧姆在他的回答中给出了原始代码的一个解释和一个固定的例子。
下面是一个替代版本，它只对临时数组进行一次分配，并使用一对共递归函数来避免数据的复制。我不知道为什么会经常使用自顶向下的合并排序，自下而上的合并排序是非递归的，速度更快，理解起来也更简单。
在我的系统中，Intel 2600K3.4GHz，这个例子可以在大约2秒内对2000万32位整数进行排序。(自下而上的合并排序大约需要1.9秒)。
void TopDownSplitMergeAtoA(int a[], int b[], size_t ll, size_t ee);
void TopDownSplitMergeAtoB(int a[], int b[], size_t ll, size_t ee);
void MergeRuns(int a[], int b[], size_t ll, size_t rr, size_t ee);
void TopDownMergeSort(int a[], size_t n)
{
int *b;
if(n < 2) // if size < 2 return
return;
b = malloc(n * sizeof(int)); // one time allocation
TopDownSplitMergeAtoA(a, b, 0, n);
free(b);
return;
}
void TopDownSplitMergeAtoA(int a[], int b[], size_t ll, size_t ee)
{
size_t rr;
if((ee - ll) == 1) // if size == 1 return
return;
rr = (ll + ee)>>1; // midpoint, start of right half
TopDownSplitMergeAtoB(a, b, ll, rr);
TopDownSplitMergeAtoB(a, b, rr, ee);
MergeRuns(b, a, ll, rr, ee); // merge b to a
}
void TopDownSplitMergeAtoB(int a[], int b[], size_t ll, size_t ee)
{
size_t rr;
if((ee - ll) == 1){ // if size == 1 copy a to b
b[ll] = a[ll];
return;
}
rr = (ll + ee)>>1; // midpoint, start of right half
TopDownSplitMergeAtoA(a, b, ll, rr);
TopDownSplitMergeAtoA(a, b, rr, ee);
MergeRuns(a, b, ll, rr, ee); // merge a to b
}
void MergeRuns(int a[], int b[], size_t ll, size_t rr, size_t ee)
{
size_t o = ll; // b[] index
size_t l = ll; // a[] left index
size_t r = rr; // a[] right index
while(1){ // merge data
if(a[l] <= a[r]){ // if a[l] <= a[r]
b[o++] = a[l++]; // copy a[l]
if(l < rr) // if not end of left run
continue; // continue (back to while)
while(r < ee) // else copy rest of right run
b[o++] = a[r++];
break; // and return
} else { // else a[l] > a[r]
b[o++] = a[r++]; // copy a[r]
if(r < ee) // if not end of right run
continue; // continue (back to while)
while(l < rr) // else copy rest of left run
b[o++] = a[l++];
break; // and return
}
}
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/32936304
复制相关文章
相似问题
腾讯云开发者
