int lb = 0, ub = 8, mid; //ub=upper bound,lb=lower bound.
int i = 0, j = 0, k = 0;
int a[] = { 15, 5, 24, 8, 1, 3, 16, 10, 20 };
int b[10];
void mergeSort(int a[], int lb, int ub) {
if (lb < ub) {
mid = ((lb + ub) / 2);
mergeSort(a, lb, mid);
mergeSort(a, mid + 1, ub);
merge(a, lb, mid, ub);
}
}
void merge(int a[], int lb, int mid, int ub) {
i = lb;
j = mid + 1;
k = lb;
while (i <= mid && j <= ub) {
if (a[i] <= a[j]) {
b[k] = a[i];
i++;
} else {
b[k] = a[j];
j++;
}
k++;
}
if (i > mid) {
while (j <= ub) {
b[k] = a[j];
j++;
k++;
}
} else {
while (i <= mid) {
b[k] = a[i];
i++;
k++;
}
}
for (k = lb; k <= ub; k++) {
a[k] = b[k];
}
}
void printList(int A[]) {
for (k = 0; k <= 8; k++) {
printf("%d\n", A[k]);
}
printf("done\n");
}
int main() {
printList(a);
mergeSort(a, 0, 8);
printList(a);
}
[我认为mergesort
和merge
的代码不是问题,问题是我已多次检查代码,但是我找不到错误,所以希望有人可以向我解释问题所在,感谢所有尝试提供帮助的人!
运行代码时的输出:
51581个316102024做完了
不是排序列表。
问题是mid
是全局变量,因此它被递归调用mergeSort(a, lb, mid);
修改,并且第二个递归调用mergeSort(a, mid + 1, ub);
使用了另一个值,而最终调用[[ C0]产生意外结果,并可能导致不确定的行为。
请勿使用全局变量。在merge(a, lb, mid, ub);
中定义两个数组,在main
和i
中使j
,k
,mid
和merge
局部变量并将辅助数组mergeSort
传递到b
和merge
。
这里是修改后的版本:
mergeSort
输出:
之前:15 5 24 8 1 3 16 10 20之后:1 3 5 8 10 15 16 20 24
请注意,在切片的最后一个切片之后,将#include <stdio.h>
void merge(int a[], int lb, int mid, int ub, int b[]) {
int i = lb;
int j = mid + 1;
int k = lb;
while (i <= mid && j <= ub) {
if (a[i] <= a[j]) {
b[k] = a[i];
i++;
} else {
b[k] = a[j];
j++;
}
k++;
}
if (i > mid) {
while (j <= ub) {
b[k] = a[j];
j++;
k++;
}
} else {
while (i <= mid) {
b[k] = a[i];
i++;
k++;
}
}
for (k = lb; k <= ub; k++) {
a[k] = b[k];
}
}
void mergeSort(int a[], int lb, int ub, int b[]) {
if (lb < ub) {
int mid = (lb + ub) / 2;
mergeSort(a, lb, mid, b);
mergeSort(a, mid + 1, ub, b);
merge(a, lb, mid, ub, b);
}
}
void printList(int A[], int len) {
for (int k = 0; k < len; k++) {
printf(" %d", A[k]);
}
printf("\n");
}
int main() {
int a[] = { 15, 5, 24, 8, 1, 3, 16, 10, 20 };
int len = sizeof(a) / sizeof(a[0]);
// make b a temporary array the same size as a
int b[len];
printf("before:");
printList(a, len);
mergeSort(a, 0, len - 1, b);
printf("after:");
printList(a, len);
return 0;
}
作为索引传递给元素的索引较少出错,因此切片长度为ub
,并且不需要任何令人困惑的ub - lb
/ [C0 ]调整。此外,由于其余元素已经在目标数组中的适当位置,因此无需从右半部分复制它们。
这里是经过简化的修改版:
+1