data-structures - 对随机数组进行排序

Question

我得到一个数组，在这些数组中我可以有 10 个元素。我必须按排序顺序管理这些 celem

我尝试使用选择排序算法，但最大交换约束不允许我这样做。

任何人都可以带领我。

谢谢！

Answer 1

算法是：

1. 从数组的右侧开始，将所有 a 交换到数组的左侧。
2. 从数组的右侧开始（再次），在所有 a 之后将所有 b 交换到数组的左侧。
3. （再次）从数组右侧开始，在所有 a 和 b 之后将所有 c 交换到数组左侧。

这一切都保留了您的颜色交换限制，因为例如颜色“e”可以在步骤 1-5 的每个步骤中仅移动一次，但随后将被单独放置。

要做到这一点，您必须小心不要将颜色与相同的颜色交换（也避免这种退化的情况，即与自身交换某些东西）。

代码是这样的（带有一些非常基本的单元测试）：

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

int limit_sort(char *input, size_t n) {
    int target = 0;
    int swaps = 0;
    for (char c = 'a'; c <= 'z'; c++) {
        for (int i = n - 1; i >= 0; i--) {
            if (input[i] != c) continue;
            while (target < i && input[target] <= c) target++;
            if (target < i) {
                input[i] = input[target];
                input[target] = c;
                swaps++;
            }
        }
    }
    return swaps;
}

int main(int argc, char**argv) {
    struct {
        char *input;
        char *want;
        int want_swaps;
    } test_cases[] = {
        {"aaa", "aaa", 0},
        {"aba", "aab", 1},
        {"abc", "abc", 0},
        {"acb", "abc", 1},
        {"bbbaaa", "aaabbb", 3},
    };
    int fails = 0;
    for (int i = 0; i < sizeof(test_cases)/ sizeof(test_cases[0]); i++) {
        char t[32];
        strcpy(t, test_cases[i].input);
        int got_swaps = limit_sort(t, strlen(t));
        if (got_swaps != test_cases[i].want_swaps) {
            printf("limit_sort(%s) = %d, want %d\n", test_cases[i].input, got_swaps, test_cases[i].want_swaps);
            fails++;
        }
        if (strcmp(t, test_cases[i].want)) {
            printf("limit_sort(%s) -> %s, want %s\n", test_cases[i].input, t, test_cases[i].want);
            fails++;
        }
    }
    printf(fails ? "FAILED\n" : "OK\n");
    return fails == 0;
}