基于排序的分区（类似于快速排序）

这是一个面试问题：给定一个具有3种对象的数组，白色，红色，黑色 - 应该实现数组的排序，以便它看起来如下： {白} * {黑} * {红} *。这位技术人员说 - “你不能使用计数排序”。他的提示是想一些快速排序的相关技术。所以我建议使用一种类似快速排序的分区。他只需要使用swap每进行一次array`s element.I不`吨知道该怎么做....任何建议（我不知道，如果有可能的话）我的解决办法：基于排序的分区（类似于快速排序）

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

来源

2013-11-23 Yakov

这是一个愚蠢的例子。如果你使用计数排序，你所需要的只是3个变量，你会按照O（n）排序。如果他试图让你的东西变成别的东西，他应该给你另一个例子。 – 2013-11-23 15:49:25

面试官可能想知道你是否熟悉[荷兰国旗问题]（http://en.wikipedia.org/wiki/Dutch_national_flag_problem）。它有一个简单的线性解决方案。 – Blastfurnace

@Blastfurnace - 我明白了。我的想法是一样的（我的解决方案最小化交换元件）但是仍然经典的荷兰国旗解决方案（来自维基）有两个交换一些元素 – Yakov

你开始具有“已知为白色”值的空部分的数组，“未知”值的初始大部分以及“已知为红色”值的空白部分。

第一：

通过计数导致白色值的数量树立“已知是白”部分的大小。
通过计算结尾红色值的数量来确定“已知为红色”部分的大小。

如果两个尺寸都为零，那就好了;你只需要知道尺寸是多少。

您可以通过“未知”一节一个值在一个时间步骤：

如果下一个值是红色的，与价值交换前的最后一个“已知的红色”值，延长该部分。
如果下一个值为白色，则将其与最后一个“已知为白色”值之后的值交换，以扩展该部分。
否则，就把它留在原地。
重新开始“已知为白色”和“已知为红色”部分。

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

请注意，测试的顺序很重要（并且与此代码的原始版本相反）。由于Yakov在他的comment中指出，在当前值为红色并且“已知为红色”部分之前的值为白色的情况下，第一个测试会将红色移至“已知为红色”部分，但会移动一个白色到当前位置。然后你必须检查当前位置是否是白色并移动它。

如果这是太多的掉期，那么试试看如何做另一种方式。

此代码似乎工作。它有相当广泛的自我检查和测试。完整的调试代码可根据要求提供（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

它已经经过了几百万随机测试运行。

来源

2013-11-23 16:55:45

如果我正确理解您的解决方案 - 有时会使用相同的数组单元格完成多次交换。假设当前值为红色，并且“已知为红色”值之前的线条为白色......在这种情况下，您不应该宣传当前值索引。但再次检查是否将下一个值替换为“已知为白色”部分。 – Yakov

你是不对的！请看下面的数组：color arr4 [] = {RED，BLACK，RED，WHITE，RED，RED，BLACK，WHITE，RED，BLACK，RED，BLACK，BLACK，RED，BLACK，WHITE ，黑，白，白，白，白，红，红，红，红，黑，白};它不会给出正确的结果。 – Yakov

不仅如此，你的算法还可以进行2次白色交换。例如，颜色arr5 [] = {白色，白色，黑色，红色，黑色，黑色，红色，白色，红色}。如果它使得arr5 [] = {白色，白色，黑色，白色，黑色，黑色，红色，红色，红色}，则i = 3。在第二个，如果它使arr5 [] = {白色，白色，白色，黑色，黑色，黑色，红色，红色，红色};问题是不做2次掉期。 – Yakov

基于排序的分区（类似于快速排序）

回答

相关问题