我尝试使用C 实现一些纯通用的算法。我坚持使用3向快速排序但不知何故实现不能提供正确的输出。 输出几乎排序,但有些键不在应有的位置。 代码如下。 提前致谢。
#include #include #include #include static void swap(void *x, void *y, size_t size) { void *tmp = malloc(size); memcpy(tmp, x, size); memcpy(x, y, size); memcpy(y, tmp, size); free(tmp); } static int cmpDouble(const void *i, const void *j) { if (*(double *)i < *(double *)j) return 1; else if (*(double *)i == *(double *)j) return 0; else return -1; } void qsort3way(void *base, int lo, int hi, size_t size, int (*cmp)(const void *, const void *)) { if (hi <= lo) return; else { char *ptr = (char*)base; char *v = ptr + lo * size; int lt = lo, gt = hi; int i = lo; while (i <= gt) { int c = cmp(v, ptr + i * size); if (c 0) swap(ptr + i * size, ptr + (gt--) * size, size); else i++; } qsort3way(base, lo, lt - 1, size, cmp); qsort3way(base, gt + 1, hi, size, cmp); } } int main(void) { int i; double *d = (double*)malloc(sizeof(double) * 100); for (i = 0; i < 100; i++) d[i] = (double)rand(); qsort3way(d, 0, 100 -1, sizeof(double), cmpDouble); for (i = 0; i < 100; i++) printf("%.10lfn", d[i]); free(d); return 0; }
样本输出:
41.0000000000 153.0000000000 288.0000000000 2082.0000000000 292.0000000000 1869.0000000000 491.0000000000 778.0000000000 1842.0000000000 6334.0000000000 2995.0000000000 8723.0000000000 3035.0000000000 3548.0000000000 4827.0000000000 3902.0000000000 4664.0000000000 5436.0000000000 4966.0000000000 5537.0000000000 5447.0000000000 7376.0000000000 5705.0000000000 6729.0000000000 6868.0000000000 7711.0000000000 9961.0000000000 8942.0000000000 9894.0000000000 9040.0000000000 9741.0000000000
您的实现不正确,因为在分区阶段枢轴可能会移动,并且您使用指针进行比较,而不再指向它。 其他语言的实现使用pivot的值而不是其地址。
还要注意这些缺点:
这是一个更正和评论的版本:
#include #include static void swap(unsigned char *x, unsigned char *y, size_t size) { /* sub-optimal, but better than malloc */ while (size-- > 0) { unsigned char c = *x; *x++ = *y; *y++ = c; } } void qsort3way(void *base, int n, size_t size, int (*cmp)(const void *, const void *)) { unsigned char *ptr = (unsigned char *)base; while (n > 1) { /* use first element as pivot, pointed to by lt */ int i = 1, lt = 0, gt = n; while (i < gt) { int c = cmp(ptr + lt * size, ptr + i * size); if (c > 0) { /* move smaller element before the pivot range */ swap(ptr + lt * size, ptr + i * size, size); lt++; i++; } else if (c < 0) { /* move larger element to the end */ gt--; swap(ptr + i * size, ptr + gt * size, size); /* test with that element again */ } else { /* leave identical element alone */ i++; } } /* array has 3 parts: * from 0 to lt excluded: elements smaller than pivot * from lt to gt excluded: elements identical to pivot * from gt to n excluded: elements greater than pivot */ /* recurse on smaller part, loop on larger to minimize stack use for pathological distributions */ if (lt < n - gt) { qsort3way(ptr, lt, size, cmp); ptr += gt * size; n -= gt; } else { qsort3way(ptr + gt * size, n - gt, size, cmp); n = lt; } } } static int cmp_double(const void *i, const void *j) { /* this comparison function does not handle NaNs */ if (*(const double *)i < *(const double *)j) return -1; if (*(const double *)i > *(const double *)j) return +1; else return 0; } int main(void) { double d[100]; int i; for (i = 0; i < 100; i++) d[i] = rand() / ((double)RAND_MAX + 1); qsort3way(d, 100, sizeof(*d), cmp_double); for (i = 0; i < 100; i++) printf("%.10lfn", d[i]); return 0; }
阅读了您提供给@JohnBollinger的图书链接 。 我理解你的算法如何工作。 您的问题是您的枢轴移动,但您没有更改v
的值。 您的轴位于索引lt
char *ptr = base; int lt = lo, gt = hi; // lt is the pivot int i = lo + 1; // we don't compare pivot with itself while (i <= gt) { int c = cmp(ptr + lt * size, ptr + i * size); if (c < 0) { swap(ptr + lt++ * size, ptr + i++ * size, size); } else if (c > 0) swap(ptr + i * size, ptr + gt-- * size, size); else i++; } qsort3way(base, lo, lt - 1, size, cmp); qsort3way(base, gt + 1, hi, size, cmp);
我建议你一个“适当”的解决方案:
#include #include #include typedef void qsort3way_swap(void *a, void *b); typedef int qsort3way_cmp(void const *a, void const *b); static void qsort3way_aux(char *array_begin, char *array_end, size_t size, qsort3way_cmp *cmp, qsort3way_swap *swap) { if (array_begin < array_end) { char *i = array_begin + size; char *lower = array_begin; char *greater = array_end; while (i < greater) { int ret = cmp(lower, i); if (ret < 0) { swap(i, lower); i += size; lower += size; } else if (ret > 0) { greater -= size; swap(i, greater); } else { i += size; } } qsort3way_aux(array_begin, lower, size, cmp, swap); qsort3way_aux(greater, array_end, size, cmp, swap); } } static void qsort3way(void *array_begin, void *array_end, size_t size, qsort3way_cmp *cmp, qsort3way_swap *swap) { qsort3way_aux(array_begin, array_end, size, cmp, swap); } static void swap_int_aux(int *a, int *b) { int tmp = *a; *a = *b; *b = tmp; } static void swap_int(void *a, void *b) { swap_int_aux(a, b); } static int cmp_int_aux(int const *a, int const *b) { if (*a < *b) { return 1; } else if (*a > *b) { return -1; } else { return 0; } } static int cmp_int(void const *a, void const *b) { return cmp_int_aux(a, b); } static void print_int(char const *intro, int const *array, size_t const size) { printf("%s:", intro); for (size_t i = 0; i < size; i++) { printf(" %d", array[i]); } printf("n"); } #define SIZE 42 int main(void) { int array[SIZE]; srand((unsigned int)time(NULL)); for (size_t i = 0; i < SIZE; i++) { array[i] = rand() % SIZE - SIZE / 2; } print_int("before", array, SIZE); qsort3way(array, array + SIZE, sizeof *array, cmp_int, swap_int); print_int("after", array, SIZE); }
注意:优化int i = lo + 1;
和char *i = array_begin + size;
是必须的。 因为在函数比较返回pivot != pivot
的情况下,这将导致无限递归。 这怎么可能?
实现没有给出正确的结果,因为它是错误的 。 事实上,这是非常错误的,因为它应该是一个三向快速排序而不是常规排序。
一个基本问题是您在主分区循环后省略了将枢轴移动到其正确位置的位。 对于标准快速排序,在循环之后需要一次额外的交换或分配,具体取决于实现细节。 对于包含一个或两个额外循环的三向快速排序,将潜在的多个值等于枢轴移动到它们的位置。
一个更阴险的问题是@Stargateur首先指出:你通过指针而不是值来跟踪枢轴元素,并且你(有时)在分区循环过程中将原始值从该位置交换出来。
此外,对于三向快速排序,您的主分区循环也是错误的。 当您遇到与枢轴相等的元素时,您只需将其保留在原位,但您需要将其移动到一端或另一端(或者某种辅助存储,如果您愿意承担内存成本)你可以在最后移动到中间。 从某种意义上说,前一个问题是这个问题的一个特例 – 你没有为枢轴值保留空间或跟踪它。 修复此问题也将解决以前的问题。
我不确定你用什么参考来准备你的实现,或者你是否从头开始构建它,但Geeks for Geeks有一个C ++(但几乎也是C) 实现你可能想要检查的int
数组 。
以上就是c/c++开发分享3路快速排序(C实现)相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注计算机技术网(www.ctvol.com)!)。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/562580.html