我正在尝试实现一种可以处理整数、字符串和字符的合并排序算法。不幸的是,我发现当数组长度为奇数时,它不能正确处理整数。
例如:输入:2 2 3 7 1 2 1
。输出:2 2 3 7 0 1 1
。
现在我正试图找出我的代码中的错误。在这里:
#include <stddef.h>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include "MergeSort.h"
int StrCmp(char *st1, char *st2) {
char *str1 = st1, *str2 = st2;
while (*str1 == *str2 && *str1 != 0)
str1++, str2++;
return *str1 - *str2;
}
int CompareInt(void *a, void *b) {
return *(int *)a - *(int *)b;
}
int CompareChar(void *a, void *b) {
return *(char *)a - *(char *)b;
}
int CompareStr(const void *a, const void *b) {
return strcmp(*(char **)a, *(char **)b);
}
int merge(void *base, size_t num, size_t el_size, int (*compar)(const void*, const void*)) {
size_t size = (size_t)num / 2;
char *char_base = (char *)base;
char *first = malloc(size * el_size);
char *second = malloc((num - size) * el_size);
for (int i = 0; i < size; i++)
for (int j = 0; j < el_size; j++)
first[i * el_size + j] = char_base[i * el_size + j];
for (int i = 0; i < num - size; i++)
for (int j = 0; j < el_size; j++)
second[i * el_size + j] = char_base[size * el_size + i * el_size + j];
size_t i = 0, j = 0, c = 0;
while (i < size && j < num - size) {
if (compar(&first[i * el_size], &second[j * el_size]) <= 0) {
for (int k = 0; k < el_size; k++)
char_base[el_size * c + k] = first[i * el_size + k];
i++;
} else {
for (int k = 0; k < el_size; k++)
char_base[el_size * c + k] = second[j * el_size + k];
j++;
}
c++;
}
if (i == size) {
while (j < num - size) {
for (int k = 0; k < el_size; k++)
char_base[el_size * c + k] = second[j * el_size + k];
j++;
c++;
}
} else {
while (i < size) {
for (int k = 0; k < el_size; k++)
char_base[el_size * c + k] = first[i * el_size + k];
i++;
c++;
}
}
free(first);
free(second);
}
int merge_sort(void *base, size_t num, size_t el_size, int (*compar)(const void*, const void*)) {
if (num > 1) {
size_t s = num / 2;
char *char_base = base;
merge_sort(char_base, s, el_size, compar);
merge_sort(char_base + (num - s) * el_size, num - s, el_size, compar);
merge(char_base, num, el_size, compar);
}
}
int main() {
int nums[] = { 2, 2, 3, 7, 1, 2, 1 };
cmp_t cmp = CompareInt;
merge_sort(nums, 7, sizeof(int), cmp);
for (int i = 0; i < 7; i++)
printf("%i ", nums[i]);
return 0;
}
最佳答案
错误在函数 merge_sort()
中:第二次递归调用是在错误的基地址上完成的:
merge_sort(char_base + (num - s) * el_size, num - s, el_size, compar);
修复是用
merge_sort(char_base + s * el_size, num - s, el_size, compar);
请注意,您的代码中还有其他问题:
比较函数的签名不正确,它们应该采用
const void *
参数。merge()
和merge_sort()
都应定义为void
,因为它们不返回任何值。CompareInt
无法处理差值超过INT_MAX
的大整数值,例如INT_MAX
和INT_MIN
.应该写成:int CompareInt(const void *a, const void *b) { int na = *(const int *)a; int nb = *(const int *)b; return (nb < na) - (na < nb); }
你应该在数字后打印一个
'\n'
。
您还可以通过各种方式改进实现:
如果您将
s
计算为(n + 1)/2
,您可以使用更少的内存并获得更简单和更快的实现,因为您不需要merge
函数中的second
数组。使用指针,您将大大减少乘法运算的次数。
这是一个具有相同语义的更简单的实现:
void merge(void *base, size_t num, size_t el_size, size_t size,
int (*compar)(const void*, const void*)) {
size_t split = size * el_size;
char *first = malloc(split);
char *p1 = memcpy(first, base, split);
char *dest = base, *p2 = dest + split;
size_t i = 0, j = size;
while (i < size) {
if (j == num || compar(p1, p2) <= 0) {
for (size_t k = 0; k < el_size; k++)
*dest++ = *p1++;
i++;
} else {
for (size_t k = 0; k < el_size; k++)
*dest++ = *p2++;
j++;
}
}
free(first);
}
void merge_sort(void *base, size_t num, size_t el_size,
int (*compar)(const void*, const void*)) {
if (num > 1) {
size_t s = (num + 1) / 2;
char *char_base = base;
merge_sort(char_base, s, el_size, compar);
merge_sort(char_base + s * el_size, num - s, el_size, compar);
merge(char_base, num, el_size, s, compar);
}
}
关于c - 多种类型的归并排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39884523/