在 C 中找不到此合并排序程序中的错误。始终显示分段错误

Question

我在C语言中找不到这个合并排序程序的错误。 它始终显示分段错误。

顺便说一下，这是我的合并排序代码：

我认为问题可能出在这里：

void merge(int *a, int i, int mid, int n) {
int l, m, k, b[10];
l = i;
m = mid + 1;
k = 0;
while (l <= mid && m <= n) {
if (a[l] > a[m])
b[k++] = a[l++];
if (a[m] > a[l])
b[k++] = a[m++];
}
while (l <= mid)
b[k++] = a[l++];
while (m <= n)
b[k++] = a[m++];
for (k = 0; k < n; k++)
a[i++] = b[k];
return ;
}

Answer 1

在函数的末尾(在其他地方..(：

for(k=0;k<n;k++)   // k = [0 -> n)
a[i++]=b[k];   // but b is declared as int b[10], this is surely not right.

上面的循环意味着你期望b在某个时候准确地持有n元素。 为什么"b"的大小不正确？

Answer 2

代码中存在多个问题：

• mid参数似乎是左半部分最后一个元素的索引，n右半部分最后一个元素的索引。这与 C 语言中的常见做法不一致，i是左半部分的索引，mid应该是右半部分第一个元素的索引，n应该是右半部分以外第一个元素的索引。这样，通过从最后一个元素之外的索引中减去初始索引，可以轻松计算数组长度。

• b在本地分配为大小为10的数组。 如果要合并的块的大小大于 10，则这是不正确的。 您可以使用malloc()分配一个包含(n - i)元素的数组，也可以定义一个本地数组，int b[n - i];如果要排序的数组的大小不太大(对于现代 64 位环境，少于 100 万个条目(。

• 对于局部变量的名称来说，l是一个糟糕的选择：它在图形上太接近1，造成潜在的错误和混乱。

• 主合并循环中的测试既冗余又不完整：您不处理左半部分元素等于右半部分元素的情况。

• 最后一个循环，将合并的数据复制回源数组是有缺陷的：它应该读：

  for (k = 0; k < n - i; k++)
  a[i++] = b[k];
  

以下是中等小数组的更正版本：

void merge(int *a, int start, int mid, int end) {
int i, j, k, b[end - start];
i = start;
j = mid;
k = 0;
while (i < mid && j < n) {
if (a[i] <= a[j])
b[k++] = a[i++];
else
b[k++] = a[j++];
}
while (i < mid) {
b[k++] = a[i++];
}
while (j < n) {
b[k++] = a[j++];
}
for (i = start, k = 0; i < end; i++, k++) {
a[i] = b[k];
}
}
void mersort(int *a, int length) {
if (length > 1) 
int mid = length / 2;
mergesort(a, mid);
mergesort(a + mid, length - mid);
merge(a, 0, mid, length);
}
}