c -如何使用排序数组与结构项使用归并排序?

Question

这是我为merge函数编写的代码

void merge(struct record *record_arr, int low, int mid, int high) {
int i, j, k;
int n1 = mid - low + 1;
int n2 = high - mid;
struct record *tmp1 = (struct record *)allocate_memory((n1 + 1) * sizeof(struct record));
struct record *tmp2 = (struct record *)allocate_memory((n2 + 1) * sizeof(struct record));
for (i = 0; i <= n1; i++) {
tmp1[i] = record_arr[low + i];
}
for (j = 0; j <= n2; j++) {
tmp2[j] = record_arr[mid + 1 + j];
}
tmp1[i + 1] = (struct record){ 0 };
tmp2[j + 1] = (struct record){ 0 };
i = j = 0;
for (k = low; k <= high; k++) {
if ((cmp_record(tmp1 + i, tmp2 + j) == 0) || (cmp_record(tmp1 + i, tmp2 + j) == -1)) {
record_arr[k] = tmp1[i];
i++;
} else {
record_arr[k] = tmp2[j];
j++;
}
}
}

在实现它之后，数组没有排序，我得到这个错误

Running TEST2 for 10 inputs
array is not sorted
test2: lib.c:527: check_array_is_sorted_by_uid: Assertion `0' failed.
Aborted

Answer 1

您的实现依赖于一种容易出错的技术，称为哨兵，其中在片的末尾插入一个已知大于所有有效值的值。这不是一个好主意，相反，您应该比较索引值，并且只比较片内的结构。

还需要注意，只有左侧切片需要保存，右侧切片中的结构在比较之前永远不会被覆盖。

此外，您调用比较函数两次并测试显式返回值0和-1。您应该只测试<= 0以确定要复制哪个结构。

为副本分配的内存必须在merge函数结束时释放，否则内存将丢失。

修改后的版本:

void mergesort(struct record *record_arr, int low, int high) {
if (low < high) {
int mid = low + (high - low) / 2;
mergesort(record_arr, low, mid);
mergesort(record_arr, mid + 1, high);
merge(record_arr, low, mid, high);
}
}
void merge(struct record *record_arr, int low, int mid, int high) {
int i, j, k;
int n1 = mid - low + 1;
int n2 = high - mid;
// save structures from the left slice
struct record *tmp1 = (struct record *)allocate_memory(n1 * sizeof(struct record));
for (i = 0; i < n1; i++) {
tmp1[i] = record_arr[low + i];
}
i = 0;
j = mid + 1;
k = low;
while (i < n1 && j <= high) {
if (cmp_record(tmp1 + i, record_arr + j) <= 0) {
record_arr[k++] = tmp1[i++];
} else {
record_arr[k++] = record_arr[j++];
}
}
while (i < n1) {
record_arr[k++] = tmp1(i++];
}
free_memory(tmp1);
}