原地算法系列

写完《O(n) 原地归并的稳定版本》后，我觉得我又行了，打算开坑原地算法系列。

已发布文章，新文章会在这里更新：

建了个仓库，快来玩 axiomofchoice-hjt/TCS-Algorithms (opens new window)。

原地归并 - 不稳定稳定
原地划分 - 稳定
原地反划分 - 稳定
原地选择 - 不稳定稳定
原地排序 $O(n\log n)$ 比较 $O(n\log n)$ 移动 - 不稳定 (堆排序) 稳定 (基于原地归并的归并排序)
原地排序 $O(n^2)$ 比较 $O(n)$ 移动 - 不稳定 (选择排序) 稳定
原地排序 $O(n\log n)$ 比较 $O(n)$ 移动 - 不稳定稳定

# 1. 原地算法的严谨定义

讨论学术算法时，原地的含义就是额外空间复杂度为 $O(1)$ ，那怎么定义额外空间复杂度呢？

我们从图灵机开始说起。

# 1.1. 图灵机模型

众所周知，图灵机由无限长纸带、读写头和状态寄存器组成，纸带上是离散的存储单元，存储有限字符集里的一个字符。

但是图灵机并不适合作为大多数算法的模型，它和现实机器差太远了。

第一，从时间角度。指定一个地址读取元素，又叫随机访存，图灵机需要 $O(n)$ 时间复杂度（把读写头移过去），黄花菜都凉了。

第二，从空间角度。由于字符集是有限的，存储纸带上的一个地址需要 $O(\log n)$ 个存储单元，这已经不满足“原地”的要求了。

# 1.2. RAM (Random Access Machine) 模型

为了解决图灵机的痛点，RAM 模型的做法很直接。RAM 引入了一个内存，允许常数时间完成随机访存。同时，每个存储单元可以存放任意整数。

RAM 的模型能力一下子就变得非常强大，而且强大过头了，以至于所有算法都可以改造成原地算法。这是因为我们可以轻松在 1 个存储单元里编码近乎无限的信息，把额外内存都编码进去，就实现了常数空间复杂度。

# 1.3. Word RAM 模型

在 RAM 基础上进行修正，就有了 Word RAM 模型。Word RAM 模型的存储单元是 Word，可容纳 w 比特，要求刚好能表示内存里每个存储单元的地址（没错在 C 语言里就是 size_t）。一个 Word 能存储指针，但是存不了更多的信息。

Word RAM 模型不仅足够强大，同时恰好解决了 RAM 模型的漏洞，因此它成为算法分析的事实标准。

这里不得不提 Word 压位“作弊”，借助位运算可以把 w 个 bool 压到一个 Word 里。这在原地算法领域是有争议的，反对者认为应该禁止位运算阻止这个操作。

# 2. 有没有工程意义

原地算法或许有工程意义，但我不关心工程。

很多原地算法带有巨大常数。为了让它具有工程意义，需要花很多代码、写很多边界来优化它，这与我的初衷相悖。我更关心算法的精妙，而不是反复尝试各种优化方案，一遍遍调性能。工作的性能优化已经做了很多了，业余时间还是少接触点吧。

# 3. 归并问题

归并就是合并两个有序数组。对于原地算法，只需要输入一个数组并用一个位置分割出两个有序的区间，输出就是归并后的原数组。

一个众所周知的思路是双指针归并算法，但是需要一个 $O(n)$ 大小的 buffer 数组，不满足原地的要求。

template <typename T>
void merge(T* first, T* mid, T* last) {
    int64_t len = last - first;
    std::vector<T> buffer(len);
    T* left_ptr = first;
    T* right_ptr = mid;
    T* buffer_ptr = buffer.data();
    while (left_ptr < mid || right_ptr < last) {
        if (right_ptr == last || (left_ptr < mid && *left_ptr <= *right_ptr)) {
            std::swap(*buffer_ptr, *left_ptr);
            left_ptr++;
            buffer_ptr++;
        } else {
            std::swap(*buffer_ptr, *right_ptr);
            right_ptr++;
            buffer_ptr++;
        }
    }
    std::swap_ranges(buffer.data(), buffer.data() + len, first);
}

如果同时想做到 $O(n)$ 和原地，算法就会比较复杂，我写了两个文章来讲：《O(n) 原地归并的不稳定版本》《O(n) 原地归并的稳定版本》。

# 4. 划分问题

划分就是输入一个数组和一个谓词，要求将谓词为真的元素排到谓词为假的元素前面。

这个原地但不稳定的双指针算法很容易想到。

template <typename T, typename Pred>
void partition(T* first, T* last, Pred pred) {
    T* mid = first;
    for (T* iter = first; iter < last; iter++) {
        if (pred(*iter)) {
            std::swap(*mid, *iter);
            mid++;
        }
    }
}

如果同时想做到 $O(n)$ 、原地和稳定，这又是一个复杂算法，我写了《O(n) 原地稳定划分》来讲这个事情。

# 5. 选择问题

选择就是 topk (nth-element)。划分整个数组为前 k - 1 小的数、第 k 小的数、剩下的数，功能等价于 std::nth_element。

经典的快速选择算法是一个随机化算法，最坏复杂度 $O(n^2)$ 不符合我们的要求。而 BFPRT 算法需要递归栈， $O(\log n)$ 额外空间复杂度，不算真正的原地。

如何消除递归栈，我写了《O(n) 原地选择的不稳定版本》来讲这个事情。

# 6. 排序问题

排序更是经典中的经典。

借助上面三个问题的思路，想要同时达成 $O(n\log n)$ 、原地、稳定的排序算法不是难题：用归并改造归并排序，或者用选择 + 划分改造快速排序。

但是我们还可以更进一步，例如限制 $O(n)$ 次移动，或者探索 $O(n)$ 时间复杂度的原地基数排序。

# 7. 原地算法：戴着镣铐跳舞

原地算法就像戴着镣铐跳舞，在最严格的空间限制下探索理论的边界。

就像《O(n) 原地归并的稳定版本》记载的，同时满足基于交换、稳定、原地、 $O(n)$ 时间复杂度的归并。看似不可能，但是看完了唯一值、分块、单双缓冲区的解法后，我不得不承认，算法的世界有太多未知。

我估计看的人不多，就当作自娱自乐了。

← O(n) 原地归并的稳定版本 O(n) 原地稳定划分→