我正在进行非递归合并排序,并且我想出了一个优化方法,可以加快它的速度。要点是,我不是先合并到一个临时缓冲区中,然后每次将其复制回数据位置,而是先在一个方向上合并,然后再在另一个方向上合并。这应该完美地工作,因为缓冲区的大小相同且数据相同。
但是,当我尝试这样做时,我的数组未完全排序。有些项目不合时宜,有时在末尾,在中间。在下面的示例中,我包括了用于测试代码的函数。
我尽了最大的努力来制作MWE,但是测试需要一些辅助功能。
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#define MIN(x, y) ((x) > (y) ? (y) : (x))
#define OPTIMIZE true // if true, then merge in alternating directions
void merge(int* src, int* dest, size_t start, size_t mid, size_t end);
void merge_sort(int* data, size_t length);
/* MERGESORT IMPLEMENTATION {{{1 */
void merge(int* src, int* dest, size_t start, size_t mid, size_t end) {
int i, j, k;
for (i = start, j = mid, k = start; i < mid && j < end; k++) {
if (src[i] > src[j]) {
dest[k] = src[j];
j++;
} else {
dest[k] = src[i];
i++;
}
}
for (; i < mid; i++, k++) {
dest[k] = src[i];
}
for (; j < end; j++, k++) {
dest[k] = src[j];
}
}
void merge_sort(int* data, size_t length) {
int* buffer = malloc(length * sizeof(int));
int swap = false;
for (size_t i = 0; i < length; i++) {
buffer[i] = data[i];
}
#if OPTIMIZE
for (size_t step = 1; step < length; step *= 2, swap = !swap) {
int* src = swap ? buffer : data;
int* dest = swap ? data : buffer;
for (size_t i = 0; i < length - step; i += (step * 2)) {
merge(src, dest, i, i + step, MIN(length, i + (step * 2)));
}
}
if (swap) {
for (size_t i = 0; i < length; i++) {
data[i] = buffer[i];
}
}
#else
for (size_t step = 1; step < length; step *= 2, swap = !swap) {
int* src = data;
int* dest = buffer;
for (size_t i = 0; i < length - step; i += (step * 2)) {
merge(src, dest, i, i + step, MIN(length, i + (step * 2)));
}
for (size_t i = 0; i < length; i++) {
data[i] = buffer[i];
}
}
#endif
free(
这似乎正在工作。注释中指出的修复:
void merge_sort(int* data, size_t length) {
int* buffer = malloc(length * sizeof(int));
int swap = false;
/* ** removed the initial copy */
#if OPTIMIZE
for (size_t step = 1; step < length; step *= 2, swap = !swap) {
int* src = swap ? buffer : data;
int* dest = swap ? data : buffer;
size_t i; /* fix, using i in 2nd loop */
for (i = 0; i < length - step; i += (step * 2)) { /* fix (removed size_t) */
merge(src, dest, i, i + step, MIN(length, i + (step * 2)));
}
for( ; i < length; i++) /* fix, copy single run if present */
dest[i] = src[i]; /* fix, copy single run if present */
}
if (swap) {
for (size_t i = 0; i < length; i++) {
data[i] = buffer[i];
}
}
#else
替代修补程序:
for (size_t step = 1; step < length; step *= 2, swap = !swap) {
int* src = swap ? buffer : data;
int* dest = swap ? data : buffer;
for (size_t i = 0; i < length; i += (step * 2)) { /* fix */
merge(src, dest, i, MIN(length, i+step), MIN(length, i+(step * 2))); /* fix */
}
版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。