看了一下之前遗留的论文，有个小算法可以记录一下。这个排序将循环排序 (cycle sort) 改造成了稳定排序，并保持 $O(n)$ 的移动次数。

参考论文：Stable in situ sorting and minimum data movement (opens new window)

1. 问题定义

排序一个数组，并且要求 $O(n^2)$ 时间复杂度、$O(n)$ 次移动、原地（$O(1)$ 空间复杂度）、稳定（排序前后相同元素顺序不变）。

2. 前置算法

2.1. 原地稳定划分

这是之前一期《O(n) 原地稳定划分》的算法，没看过也没关系，我们在这里当黑盒调用。

// Stub: delegates to std::stable_partition (non-in-place, O(n) extra space).
template <typename RandomIt, typename Pred>
RandomIt inplace_stable_partition_stub(RandomIt first, RandomIt last, Pred pred) {
    return std::stable_partition(first, last, pred);
}

2.2. 循环排序

循环排序是一个原地不稳定的排序算法。每个元素通过遍历整个数组找到它的目标位置，在此基础上用原地置换完成数组的重排。

置换或者排列有一个性质，把 n 个位置看成点，从其初始位置向目标位置连一条有向边，就会形成若干个不相交的环。

循环排序会依次处理每个环，沿着环的方向绕一圈，通过交换操作将每个元素移动到正确位置。如果目标位置已经是相同元素，那就不断下一个，直到找到不同元素。

复杂度 $O(n^2)$，移动次数 $O(n)$。

template <typename RandomIt, typename Proj>
std::tuple<RandomIt, RandomIt> destination_range(
    RandomIt first, RandomIt last, std::iter_value_t<RandomIt> key, Proj proj) {
    int64_t gt = 0;
    int64_t eq = 0;
    for (RandomIt it = first; it < last; ++it) {
        if (proj(key) > proj(*it)) {
            gt++;
        } else if (proj(key) == proj(*it)) {
            eq++;
        }
    }
    return {first + gt, first + gt + eq};
}

template <typename RandomIt, typename Proj>
void inplace_cyclesort(RandomIt first, RandomIt last, Proj proj) {
    using T = std::iter_value_t<RandomIt>;
    if (last - first <= 1) {
        return;
    }

    for (RandomIt it = first; it != last; it++) {
        while (true) {
            auto [left, right] = destination_range(first, last, *it, proj);
            if (left <= it && it < right) {
                break;
            }
            std::swap(*it, *std::find_if(left, right, [&](T x) { return proj(x) != proj(*it); }));
        }
    }
}

3. 原地稳定循环排序

要让循环排序稳定化，只要在循环排序前加一个步骤。

3.1. 处理目标范围

上面循环排序有个函数 destination_range，作用是遍历一遍数组，返回给定值的目标位置的区间。区间大小就是这个值的出现次数。

这一步要达成的目标是，每个 key 的目标区间内等于 key 的元素归位。

我们遍历每个值 key，在 key 的目标区间内，原地稳定划分等于 key 的元素。然后将区间内等于 key 的元素往右移动 x 个位置，x 是区间左边 key 的出现次数。

复杂度 $O(n^2)$，移动次数 $O(n)$。

for (std::optional<T> key = *std::ranges::min_element(first, last, {}, proj); key;
    key = unordered_upper_bound(first, last, *key, proj)) {
    auto [left, right] = destination_range(first, last, *key, proj);
    int64_t inner_sames = inplace_stable_partition_stub(left, right, [&](T x) {
        return proj(x) == proj(*key);
    }) - left;
    int64_t left_sames = std::count_if(first, left, [&](T x) { return proj(x) == proj(*key); });
    std::rotate(left, left + inner_sames, left + inner_sames + left_sames);
}

unordered_upper_bound 函数是遍历一次数组，找最小的大于 key 的元素。

template <typename RandomIt, typename Proj>
std::optional<std::iter_value_t<RandomIt>> unordered_upper_bound(
    RandomIt first, RandomIt last, std::iter_value_t<RandomIt> key, Proj proj) {
    std::optional<std::iter_value_t<RandomIt>> result;
    for (RandomIt it = first; it != last; ++it) {
        if (proj(*it) > proj(key) && (!result || proj(*it) < proj(*result))) {
            result = *it;
        }
    }
    return result;
}

3.2. 循环排序

循环排序的框架非常简单，就是一个原地置换：

for (RandomIt it = first; it != last; ++it) {
    RandomIt dest = destination(first, last, it, proj);
    while (dest != it) {
        RandomIt next_dest = destination(first, last, dest, proj);
        std::swap(*it, *dest);
        dest = next_dest;
    }
}

关键是这个 destination 怎么求。其实不难，统计 key 的左边，且不在目标区间内的 key 的出现次数 eq。然后在目标区间内数第 eq 个不等于 key 的元素，这个位置就是 destination。

template <typename RandomIt, typename Proj>
RandomIt destination(RandomIt first, RandomIt last, RandomIt key, Proj proj) {
    using T = std::iter_value_t<RandomIt>;
    auto [left, right] = destination_range(first, last, *key, proj);
    if (left <= key && key < right) {
        return key;
    }
    int64_t eq = 0;
    for (RandomIt it = first; it < key; ++it) {
        if (!(left <= it && it < right) && proj(*key) == proj(*it)) {
            eq++;
        }
    }
    RandomIt res = std::find_if(left, right, [&](T x) { return proj(x) != proj(*key); });
    for (int64_t i = 0; i < eq; ++i) {
        res = std::find_if(res + 1, right, [&](T x) { return proj(x) != proj(*key); });
    }
    return res;
}

复杂度 $O(n^2)$，移动次数 $O(n)$。

4. 补个代码

循环排序 完整实现 (opens new window)和测试 (opens new window)。

原地稳定循环排序 完整实现 (opens new window)和测试 (opens new window)。

5. 结尾

事实上这只是论文的一部分（定理 2），论文后面会讲对常数个键的数组排序，但是由于我已经实现了原地稳定划分，不需要重新研究。

$O(n^2)$ 的复杂度允许了很多“暴力”的遍历操作，因此这个算法非常简单小巧。

顺便预告下一个算法是原地稳定去重，等我有空就来聊一下。