3路快速排序(C实现)

Question

我尝试使用C 实现一些纯通用的算法.我坚持使用3向快速排序但不知何故实现不能提供正确的输出.输出几乎排序,但有些键不在应有的位置.代码如下.提前致谢.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

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 + (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);
    }     
}

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

Answer 1

您的实现不正确，因为枢轴可能在分区阶段移动，并且您使用不再指向它的指针进行比较。其他语言的实现使用主元的值而不是其地址。

还要注意这些缺点：

• 两种方式递归可能会导致病理分布上的堆栈溢出。在您的情况下，已经排序的数组是病态分布。
• 比较函数应返回相反的值：-1if a < b、+1isa > b和0if a == b。
• API 是非标准且令人困惑的：您应该传递元素的数量而不是包含边界的范围。

这是一个更正和评论的版本：

#include <stdio.h>
#include <stdlib.h>

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;
}