3路快速排序（C实现）
我尝试使用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("%.10lf\n", 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的值而不是其地址。
还要注意这些缺点：
- 两种方式的递归可能导致病理分布上的堆栈溢出。 在您的情况下，已经排序的数组是病态分布。
- 比较函数应该返回相反的值：
-1如果a < b，+1是a > b，则0如果a == b。 - API是非标准的并且令人困惑：您应该传递元素的数量而不是包含边界的范围。
这是一个更正和评论的版本：
#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("%.10lf\n", 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的情况下，这将导致无限递归。 这怎么可能？
- 函数cmp是bug。
-
double有奇怪的力量...双重可能不等于自己！ （-NAN）。
实现没有给出正确的结果，因为它是错误的 。 事实上，这是非常错误的，因为它应该是一个三向快速排序而不是常规排序。
一个基本问题是您在主分区循环后省略了将枢轴移动到其正确位置的位。 对于标准快速排序，在循环之后需要一次额外的交换或分配，具体取决于实现细节。 对于包含一个或两个额外循环的三向快速排序，将潜在的多个值等于枢轴移动到它们的位置。
一个更阴险的问题是@Stargateur首先指出：你通过指针而不是值来跟踪枢轴元素，并且你（有时）在分区循环过程中将原始值从该位置交换出来。
此外，对于三向快速排序，您的主分区循环也是错误的。 当您遇到与枢轴相等的元素时，您只需将其保留在原位，但您需要将其移动到一端或另一端（或者某种辅助存储，如果您愿意承担内存成本）你可以在最后移动到中间。 从某种意义上说，前一个问题是这个问题的一个特例 – 你没有为枢轴值保留空间或跟踪它。 修复此问题也将解决以前的问题。
我不确定你用什么参考来准备你的实现，或者你是否从头开始构建它，但Geeks for Geeks有一个C ++（但几乎也是C） 实现你可能想要检查的int数组 。