基于排序的分区（如快速排序）

这是一道面试题： 给定一个包含 3 种对象白色、红色、黑色的数组 - 应该实现数组的排序，使其看起来如下： {白色}*{黑色}*{红色}*。 面试官说——“你不能使用计数排序”。他的提示是考虑一些与快速排序相关的技术。所以我建议使用类似于快速排序分区的分区。他只要求只使用一次交换对于每个数组的元素。我不知道该怎么做......有什么建议吗？（我不确定是否可能） 我的解决方案：

typedef enum {WHITE,BLACK,RED} color;

void swap (color* p1,color* p2)
{
   color tmp;
   tmp = *p1;
   *p1 = *p2;
   *p2 = tmp;
}

void sort3(color* arr,unsigned int n)
{
    unsigned int w = 0,r = n - 1,i = 0;

    while (i <= r)
    { 

         while (arr[w] == WHITE)
         {
            w++;
         }
         while (arr[r] == RED)
         {
            r--;
         }
         i = (w > i)? w :i;
         switch (arr [i])
         {
            case WHITE:
               swap(arr + i, arr + w);
               w++;
               break;
            case RED:
            {
                    swap(arr + i,arr + r);
                    r--;
                    if (arr [i] == WHITE)
                    {
                         swap(arr + i,arr + w);
                         w++;
                    }
              break;
            }
        }
        i++;
    }
}

您从一个数组开始，其中包含“已知为白色”值的空部分、最初较大的“未知”值部分和“已知为红色”值的空部分。

First:

• 通过计算前导白色值的数量来确定“已知白色”部分的大小。
• 通过计算尾随红色值的数量来确定“已知为红色”部分的大小。

如果任一大小为零都可以；您只需要知道尺寸是多少。

您可以一次单步执行一个值：

• 如果下一个值是红色，则将其与最后一个“已知为红色”值之前的值交换，从而扩展该部分。
• 如果下一个值是白色，则将其与最后一个“已知为白色”值之后的值交换，从而扩展该部分。
• 否则，请将其留在原处。
• 建立“已知为白色”和“已知为红色”部分。

当循环结束时，所有白色物体都在开始，所有红色物体都在结束，黑色物体必须在中间。

请注意，测试的顺序很重要（并且与此代码的原始版本相反）。作为Yakov https://stackoverflow.com/users/466056/yakov指出他的comment https://stackoverflow.com/questions/20164204/sorting-based-partition-like-in-quick-sort/20165129#comment30059837_20165129，在当前值为红色且“已知为红色”部分之前的值为白色的情况下，第一个测试将红色移动到“已知为红色”部分，但将白色移动到当前位置。然后你必须检查当前位置是否是白色并移动它。

如果交换次数过多，请尝试以其他方式进行交换。

这段代码似乎有效。它有相当广泛的自检和测试。完整的调试代码可根据要求提供（GPL v3）。

/* SO 20164204 */
#define DEBUG

#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>
#include "range.h"
#include "stderr.h"
#include "debug.h"

typedef enum { WHITE, BLACK, RED } Colour;

static char colour_code(Colour c);
static void trace_colours(FILE *fp, char const *tag, Colour *data, unsigned num, size_t w, size_t r, size_t c);

static void swap(Colour *p1, Colour *p2)
{
    Colour tmp;
    tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}

static void partition3(size_t n, Colour *arr)
{
    if (n <= 1)
        return;

    size_t w = 0;
    size_t r = n;

    DB_TRACE(1, "\nw0 = %zu; r0 = %zu: ", w, r);
    while (w < r && arr[w] == WHITE)
        w++;
    while (r > w && arr[r-1] == RED)
        r--;
    DB_TRACE(1, "w1 = %zu; r1 = %zu\n", w, r);

    for (size_t i = w; i < r; i++)
    {
        DB_TRACE(1, "i = %2zu [1] w = %2zu, r = %2zu, c = %c", i, w, r, colour_code(arr[i]));
        DB_CALL(1, trace_colours(stderr, "", arr, n, w, r, i));
        if (arr[i] == RED)
        {
            swap(&arr[i], &arr[--r]);
            DB_TRACE(1, "i = %2zu [2] w = %2zu, r = %2zu, c = %c", i, w, r, colour_code(arr[i]));
            DB_CALL(1, trace_colours(stderr, "", arr, n, w, r, i));
        }
        if (arr[i] == WHITE)
        {
            swap(&arr[i], &arr[w++]);
            DB_TRACE(1, "i = %2zu [3] w = %2zu, r = %2zu, c = %c", i, w, r, colour_code(arr[i]));
            DB_CALL(1, trace_colours(stderr, "", arr, n, w, r, i));
        }
        while (r > w && arr[r-1] == RED)
            r--;
        while (w < r && arr[w] == WHITE)
            w++;
        if (i < w && w > 0)
            i = w - 1;
    }
}

/* DEBUGGING and TEST infrastructure */

static char const *colour_name(Colour c)
{
    return(c == WHITE ? "WHITE" : c == RED ? "RED" : "BLACK");
}

static char colour_code(Colour c)
{
    return(c == WHITE ? 'W' : c == RED ? 'R' : 'B');
}

static void print_colours(FILE *fp, char const *tag, Colour *data, size_t num)
{
    fprintf(fp, "%s: (%zu)", tag, num);
    for (size_t i = 0; i < num; i++)
        fprintf(fp, " %c", colour_code(data[i]));
    putc('\n', fp);
}

static void dump_colours(char const *tag, Colour *data, size_t num)
{
    print_colours(stdout, tag, data, num);
}

static void trace_colours(FILE *fp, char const *tag, Colour *data, unsigned num, size_t w, size_t r, size_t c)
{
    assert(w <= r);
    assert(r <= num);
    fprintf(fp, "%s: ", tag);
    for (unsigned i = 0; i < num; i++)
    {
        char pad = ' ';
        if (i == w || i == r)
            pad = '|';
        if (i == c)
            pad = '[';
        if (i == c+1)
            pad = ']';
        fprintf(fp, "%c%c", pad, colour_code(data[i]));
    }
    if (c == num - 1)
        putc(']', fp);
    else if (r == num || w == num)
        putc('|', fp);
    putc('\n', fp);
}

static Colour *dup_sequence(size_t n, Colour const *a)
{
    Colour *d = malloc(n * sizeof(*d));
    if (d == 0)
    {
        fprintf(stderr, "Out of memory\n");
        exit(1);
    }
    for (size_t i = 0; i < n; i++)
        d[i] = a[i];
    return d;
}

static bool is_invalid_sequence(size_t n, Colour *a, bool report)
{
    bool rc = false;
    size_t w;
    for (w = 0; w < n; w++)
    {
        if (a[w] != WHITE)
            break;
    }

    size_t b;
    for (b = w; b < n; b++)
    {
        if (a[b] == WHITE)
        {
            if (report)
            {
                fprintf(stderr, "Error: %c out of position (%zu)", colour_code(a[b]), b);
                print_colours(stderr, "", a, n);
            }
            rc = true;
        }
        if (a[b] != BLACK)
            break;
    }

    size_t r;
    for (r = b; r < n; r++)
    {
        if (a[r] != RED)
        {
            if (report)
            {
                fprintf(stderr, "Error: %c out of position (%zu)", colour_code(a[r]), r);
                print_colours(stderr, "", a, n);
            }
            rc = true;
        }
    }

    return rc;
}

static size_t seqno = 0;
static bool wflag = false;
static bool verbose = false;

typedef struct Test
{
    Colour *data;
    size_t size;
} Test;

static void write_sequence(size_t seq, size_t n, Colour *a)
{
    size_t i;
    printf("Colour seq_%03zu[] =\n{\n", seq);
    for (i = 0; i < n; i++)
    {
        printf(" %s,", colour_name(a[i]));
        if (i % 10 == 9)
            putchar('\n');
    }
    if (i %10 != 0)
        putchar('\n');
    printf("};\n");
}

static bool test_sequence(Test t)
{
    bool rc = true;
    size_t n = t.size;
    Colour *a = t.data;
    Colour *d = dup_sequence(n, a);
    if (verbose)
        dump_colours("Before", a, n);
    partition3(n, d);
    if (verbose)
        dump_colours("After ", d, n);
    if (is_invalid_sequence(n, d, false))
    {
        if (!verbose)
            dump_colours("Before", a, n);
        is_invalid_sequence(n, d, true);
        if (!verbose)
            dump_colours("After ", d, n);
        if (wflag)
            write_sequence(++seqno, n, a);
        rc = false;
    }
    free(d);
    return rc;
}

static size_t fixed_tests(char const *range, size_t *counter)
{
    size_t fail = 0;

    Colour seq_001[] = { WHITE, BLACK, RED };
    Colour seq_002[] = { WHITE, WHITE, WHITE };
    Colour seq_003[] = { RED, RED, RED };
    Colour seq_004[] = { BLACK, BLACK, BLACK };
    Colour seq_005[] = { RED, BLACK, WHITE };
    Colour seq_006[] = { WHITE, WHITE, RED, RED, BLACK, BLACK, WHITE };
    Colour seq_007[] =
    {
        BLACK, BLACK, WHITE, WHITE, RED, RED, BLACK, BLACK, WHITE,
        BLACK, BLACK,
    };
    Colour seq_008[] = { WHITE, BLACK };
    Colour seq_009[] = { BLACK, BLACK, RED, RED, WHITE, WHITE, RED };
    Colour seq_010[] = { BLACK, BLACK, RED, WHITE, RED };
    Colour seq_011[] =
    {
        RED, BLACK, RED, WHITE, RED, RED, BLACK, WHITE, RED, BLACK, RED,
        BLACK, BLACK, RED, BLACK, WHITE, BLACK, WHITE, WHITE, WHITE,
        WHITE, RED, RED, RED, RED, BLACK, WHITE
    };
    Colour seq_012[] =
    {
        WHITE, WHITE, RED, WHITE, RED, BLACK, RED, BLACK, WHITE, BLACK,
        RED, RED, RED, WHITE, RED, RED, BLACK, BLACK, BLACK, RED, RED,
        BLACK, BLACK, WHITE, WHITE, RED, WHITE, BLACK, RED, BLACK,
        WHITE, RED, WHITE, WHITE, RED, WHITE, BLACK, RED, RED, RED,
        WHITE,
    };
    Colour seq_013[] = { RED, WHITE, RED, };
    Colour seq_014[] = { RED, WHITE, };
    Colour seq_015[] = { RED, BLACK, };
    Colour seq_016[] = { RED, RED, };
    Colour seq_017[] = { BLACK, WHITE, };
    Colour seq_018[] = { BLACK, BLACK, };
    Colour seq_019[] = { BLACK, RED, };
    Colour seq_020[] = { WHITE, WHITE, };
    Colour seq_021[] = { WHITE, RED, };
    Colour seq_022[] = { RED, WHITE, RED, WHITE, };
    Colour seq_023[] =
    {
        RED, WHITE, RED, WHITE, RED, RED, WHITE, WHITE, WHITE,
    };
    Test tests[] =
    {
        { seq_001, sizeof(seq_001)/sizeof(seq_001[0]) },
        { seq_002, sizeof(seq_002)/sizeof(seq_002[0]) },
        { seq_003, sizeof(seq_003)/sizeof(seq_003[0]) },
        { seq_004, sizeof(seq_004)/sizeof(seq_004[0]) },
        { seq_005, sizeof(seq_005)/sizeof(seq_005[0]) },
        { seq_006, sizeof(seq_006)/sizeof(seq_006[0]) },
        { seq_007, sizeof(seq_007)/sizeof(seq_007[0]) },
        { seq_008, sizeof(seq_008)/sizeof(seq_008[0]) },
        { seq_009, sizeof(seq_009)/sizeof(seq_009[0]) },
        { seq_010, sizeof(seq_010)/sizeof(seq_010[0]) },
        { seq_011, sizeof(seq_011)/sizeof(seq_011[0]) },
        { seq_012, sizeof(seq_012)/sizeof(seq_012[0]) },
        { seq_013, sizeof(seq_013)/sizeof(seq_013[0]) },
        { seq_014, sizeof(seq_014)/sizeof(seq_014[0]) },
        { seq_015, sizeof(seq_015)/sizeof(seq_015[0]) },
        { seq_016, sizeof(seq_016)/sizeof(seq_016[0]) },
        { seq_017, sizeof(seq_017)/sizeof(seq_017[0]) },
        { seq_018, sizeof(seq_018)/sizeof(seq_018[0]) },
        { seq_019, sizeof(seq_019)/sizeof(seq_019[0]) },
        { seq_020, sizeof(seq_020)/sizeof(seq_020[0]) },
        { seq_021, sizeof(seq_021)/sizeof(seq_021[0]) },
        { seq_022, sizeof(seq_022)/sizeof(seq_022[0]) },
        { seq_023, sizeof(seq_023)/sizeof(seq_023[0]) },
    };
    enum { NUM_TESTS = sizeof(tests) / sizeof(tests[0]) };

    *counter = 0;
    if (range != 0)
    {
        const char *ptr = range;
        const char *nxt;
        long lo;
        long hi;
        while ((nxt = parse_range(ptr, &lo, &hi)) != 0)
        {
            if (nxt == ptr)
                err_error("invalid range string (%s)\n", range);
            if (hi == 0)
                hi = NUM_TESTS-1;
            for (long i = lo; i <= hi; i++)
            {
                (*counter)++;
                if (test_sequence(tests[i]) == false)
                {
                    printf("Test %ld: Failed\n", i);
                    fail++;
                }
            }
            ptr = nxt;
        }
    }
    else
    {
        for (size_t i = 0; i < NUM_TESTS; i++)
        {
            (*counter)++;
            if (test_sequence(tests[i]) == false)
            {
                printf("Test %ld: Failed\n", i);
                fail++;
            }
        }
    }

    return fail;
}

static size_t random_tests(size_t seed, size_t number, size_t maxsize)
{
    size_t fail = 0;
    srand(seed);
    printf("Seed: %zu\n", seed);

    for (size_t i = 0; i < number; i++)
    {
        Test t;
        t.size = rand() % maxsize;
        t.data = malloc(t.size * sizeof(*t.data));
        if (t.data == 0)
        {
            fprintf(stderr, "Out of memory\n");
            exit(1);
        }
        if (verbose)
            printf("Test: %zu (%zu)\n", i, t.size);
        for (size_t j = 0; j < t.size; j++)
            t.data[j] = rand() % 3;
        if (test_sequence(t) == false)
        {
            fail++;
            break;
        }
    }
    return fail;
}

int main(int argc, char **argv)
{
    static char const optstr[] = "dfm:n:o:rs:t:vw";
    static char const usestr[] = "[-dfrvw][-m maxsize][-n number][-s seed][-t tests]";
    char const *range = 0;
    unsigned seed = time(0);
    size_t number = 1000;
    size_t maxsize = 100;
    bool fixed = true;
    bool random = true;
    int opt;

    err_setarg0(argv[0]);

    while ((opt = getopt(argc, argv, optstr)) != -1)
    {
        switch (opt)
        {
        case 'd':
            db_setdebug(1);
            verbose = 1;
            break;
        case 'f':
            fixed = false;
            break;
        case 'm':
            maxsize = strtoul(optarg, 0, 0);
            break;
        case 'n':
            number = strtoul(optarg, 0, 0);
            break;
        case 'r':
            random = false;
            break;
        case 's':
            seed = atoi(optarg);
            break;
        case 't':
            range = optarg;
            break;
        case 'v':
            verbose = true;
            break;
        case 'w':
            wflag = true;
            break;
        default:
            err_usage(usestr);
            break;
        }
    }
    if (optind != argc)
        err_usage(usestr);

    size_t fail = 0;

    if (fixed)
    {
        size_t counter;
        fail = fixed_tests(range, &counter);
        printf("Failures: %zu in %zu fixed tests\n", fail, counter);
    }
    if (fail == 0 && random)
    {
        fail = random_tests(seed, number, maxsize);
        printf("Failures: %zu in %zu random tests\n", fail, number);
    }

    return 0;
}

示例输出：

Before: (3) W B R
After : (3) W B R
Before: (3) W W W
After : (3) W W W
Before: (3) R R R
After : (3) R R R
Before: (3) B B B
After : (3) B B B
Before: (3) R B W
After : (3) W B R
Before: (7) W W R R B B W
After : (7) W W W B B R R
Before: (11) B B W W R R B B W B B
After : (11) W W W B B B B B B R R
Before: (2) W B
After : (2) W B
Before: (7) B B R R W W R
After : (7) W W B B R R R
Before: (5) B B R W R
After : (5) W B B R R
Before: (27) R B R W R R B W R B R B B R B W B W W W W R R R R B W
After : (27) W W W W W W W W B B B B B B B B R R R R R R R R R R R
Before: (41) W W R W R B R B W B R R R W R R B B B R R B B W W R W B R B W R W W R W B R R R W
After : (41) W W W W W W W W W W W W W B B B B B B B B B B B R R R R R R R R R R R R R R R R R
Before: (3) R W R
After : (3) W R R
Before: (2) R W
After : (2) W R
Before: (2) R B
After : (2) B R
Before: (2) R R
After : (2) R R
Before: (2) B W
After : (2) W B
Before: (2) B B
After : (2) B B
Before: (2) B R
After : (2) B R
Before: (2) W W
After : (2) W W
Before: (2) W R
After : (2) W R
Before: (4) R W R W
After : (4) W W R R
Before: (9) R W R W R R W W W
After : (9) W W W W W R R R R
Failures: 0 in 23 fixed tests
Seed: 1385363222
Test: 0 (0)
Before: (0)
After : (0)
Test: 1 (7)
Before: (7) W B W R W R W
After : (7) W W W W B R R
Test: 2 (1)
Before: (1) B
After : (1) B
Test: 3 (4)
Before: (4) B R R W
After : (4) W B R R
Test: 4 (3)
Before: (3) R R W
After : (3) W R R
Test: 5 (8)
Before: (8) R W R B B W W B
After : (8) W W W B B B R R
Test: 6 (3)
Before: (3) B R R
After : (3) B R R
Test: 7 (7)
Before: (7) W B W R W W W
After : (7) W W W W W B R
Test: 8 (4)
Before: (4) W B W W
After : (4) W W W B
Test: 9 (0)
Before: (0)
After : (0)
Test: 10 (6)
Before: (6) R R R W B W
After : (6) W W B R R R
Test: 11 (3)
Before: (3) R W W
After : (3) W W R
Test: 12 (5)
Before: (5) W B W R B
After : (5) W W B B R
Test: 13 (7)
Before: (7) R B R B W R B
After : (7) W B B B R R R
Test: 14 (5)
Before: (5) W W R R B
After : (5) W W B R R
Test: 15 (3)
Before: (3) W B B
After : (3) W B B
Test: 16 (5)
Before: (5) R B W W R
After : (5) W W B R R
Test: 17 (3)
Before: (3) B W B
After : (3) W B B
Test: 18 (2)
Before: (2) R B
After : (2) B R
Test: 19 (9)
Before: (9) R B R W B R B W R
After : (9) W W B B B R R R R
Failures: 0 in 20 random tests

它已经经过了数百万次随机测试。