gpt4 book ai didi

c - 归并排序: Incorrect answer

转载 作者:行者123 更新时间:2023-11-30 17:30:17 29 4
gpt4 key购买 nike

我正在尝试实现“算法简介”一书中所述的合并排序算法。尽管实现是按照书中指定的,但输出不正确。很有可能出现相差一的错误,但我无法指出它。有什么指点吗?

#include <stdio.h>
#include <stdlib.h>
#define SENTINEL 32767

int* getArray(int size) {
int* arr;
int i;

arr = (int*) malloc(sizeof(int) * size);

printf("\nEnter %d elements:\n\n", size);

for (i = 0; i < size; ++i) {
scanf("%d", (arr + i));
}

printf("\n");

return arr;
}

void printArray(int* arr, int size) {
int i;
printf("Array[%d]: ", size);
for (i = 0; i < size; ++i) {
printf("%d ", arr[i]);
}
printf("\n");
}

void merge(int* arr, int p, int q, int r) {
int i, j, k, n1, n2;
int* left;
int* right;

n1 = q - p;
n2 = r - q;

left = (int*) malloc(sizeof(int) * (n1 + 1));
right = (int*) malloc(sizeof(int) * (n2 + 1));

left[n1] = right[n2] = SENTINEL;

for (i = 0; i < n1; ++i) {
left[i] = arr[p + i];
}

for (j = 0; j < n2; ++j) {
right[j] = arr[q + j];
}

i = j = 0;

for (k = p; k < r; ++k) {
if (left[i] <= right[j]) {
arr[k] = left[i++];
} else {
arr[k] = right[j++];
}
}

}

void mergeSort(int* arr, int p, int r) {
if (p < r) {
int q = (p + r) / 2;
mergeSort(arr, p, q);
mergeSort(arr, q + 1, r);
merge(arr, p, q, r);
}
}

int main() {
int* arr;
int size;

printf("Enter array size: ");
scanf("%d", &size);

arr = getArray(size);
printArray(arr, size);

mergeSort(arr, 0, size);
printArray(arr, size);

return 0;
}

最佳答案

mergeSort 必须采用以下方式,原因已在注释中说明。

void mergeSort(int* arr, int p, int r) {
if (r - p > 1) {//for call(a, 0, 1) -> call(a, 0, 1)
int q = (p + r) / 2;
mergeSort(arr, p, q);
mergeSort(arr, q, r);
merge(arr, p, q, r);
}
}

还需要free(left);free(right);free(arr);

关于c - 归并排序: Incorrect answer,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/25191592/

29 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com