使用附加数据结构的线性排序（O(1) 找到集合的中值，O(1) 添加元素）
Linear sorting using additional data structure (O(1) to find median of set, O(1) for adding element)
假设我们在数组中有任意元素（我们可以在 O(1) 中比较它们），在魔法 DS 中我们可以在 O(1) 中添加元素并在 O(1) 中找到 DS 中元素的中值.我们不能从 DS 中删除元素，并且数组中没有相等的元素。此外，我们可以根据需要创建任意数量的此类 DS。
问题：有没有办法使用这个 DS 在 O(n) 中对数组进行排序？
是的，如果这个数据结构存在那么它可以在 O(n) 时间内用于排序。
- 扫描数组以找到最小和最大元素。调用此
min 和 max.
- 以任意顺序将所有数组元素插入数据结构。
- 插入 n - 1 份
min - 1。中位数现在是原始数组中的最小元素。
- 重复 n - 1 次：
- 插入两份
max + 1。
- 读出中位数，它现在将是原始数组中升序排列的下一个元素。
这个过程需要 O(n) 时间，因为
- 找到最小值和最大值是 O(n)，
- 插入n个元素是n * O(1) = O(n),
- 插入 n-1 个元素是 (n - 1) * O(1) = O(n),
- 插入两个元素并读取中位数是O(1)，所以这样做n - 1次是O(n)。
假设我们在数组中有任意元素（我们可以在 O(1) 中比较它们），在魔法 DS 中我们可以在 O(1) 中添加元素并在 O(1) 中找到 DS 中元素的中值.我们不能从 DS 中删除元素，并且数组中没有相等的元素。此外，我们可以根据需要创建任意数量的此类 DS。
问题：有没有办法使用这个 DS 在 O(n) 中对数组进行排序？
是的，如果这个数据结构存在那么它可以在 O(n) 时间内用于排序。
- 扫描数组以找到最小和最大元素。调用此
min和max. - 以任意顺序将所有数组元素插入数据结构。
- 插入 n - 1 份
min - 1。中位数现在是原始数组中的最小元素。 - 重复 n - 1 次：
- 插入两份
max + 1。 - 读出中位数，它现在将是原始数组中升序排列的下一个元素。
- 插入两份
这个过程需要 O(n) 时间，因为
- 找到最小值和最大值是 O(n)，
- 插入n个元素是n * O(1) = O(n),
- 插入 n-1 个元素是 (n - 1) * O(1) = O(n),
- 插入两个元素并读取中位数是O(1)，所以这样做n - 1次是O(n)。