algorithm - 有线性时间复杂度O(1)辅助空间复杂度的排序算法吗？

Question

是否有线性时间复杂度和O(1)辅助空间复杂度的排序算法来对正整数列表进行排序？我知道radix sort和 counting sort具有线性时间复杂度(O(kn) 和 O(n+k)，如果我们将 k 视为常量)，但它们都具有 O(n+k) 辅助空间复杂度。一种类型甚至有可能同时具有这两个属性吗？我们将不胜感激。

Answer 1

如果我们只对整数进行排序，我们可以使用计数排序的原位变体，它具有 O(k)空间复杂度，独立于变量 n .换句话说，当我们对待 k作为常量，空间复杂度为 O(1) .

或者，我们可以使用 in place radix sort与 lg k二进制分区的阶段 O(lg k)空间复杂度(由于递归)。甚至更少的阶段使用计数排序来确定 n 路分区的桶边界。这些解决方案的时间复杂度为 O(lg k * n) , 当仅用变量 n 表示时是O(n) (当 k 被认为是常量时)。

获取O(n)的另一种可能方法步骤复杂度和 O(1)空间复杂度，当k被认为是常数，是使用可以称为减法排序的东西，如 OP 在其 own answer 中所述, 或 elsewhere .它具有步骤复杂度 O(sum(input))哪个比 O(kn) 好(并且对于某些特定的输入，它甚至比二进制基数排序的 O(lg k * n) 更好，例如，对于 [k, 0, 0, ... 0] 形式的所有输入)和空间复杂度 O(1) .

另一种解决方案是使用 bingo sort具有步骤复杂性 O(vn)其中 v <= k是输入中唯一值的个数，空间复杂度O(1) .

请注意，这两种排序解决方案都不稳定，如果我们对不仅仅是整数(一些具有整数键的任意对象)进行排序的东西，这很重要。

在这个 paper 中也描述了一个尖端的稳定分区算法。与 O(1)空间复杂度。将其与基数排序相结合，可以构造一个空间恒定的稳定线性排序算法- O(lg k * n)步骤复杂度和 O(1)空间复杂度。

---

编辑:

根据评论的要求，我试图找到计数排序的“原位”变体的来源，但没有找到任何我可以链接到的质量好的东西(这真的很奇怪对于这样的基本算法没有容易获得的描述)。因此，我在这里发布算法:

常规计数排序(来自维基百科)

count = array of k+1 zeros
for x in input do
    count[key(x)] += 1

total = 0
for i in 0, 1, ... k do
    count[i], total = total, count[i] + total

output = array of the same length as input
for x in input do
    output[count[key(x)]] = x
    count[key(x)] += 1 

return output

它假设输入由一些对象组成，这些对象可以由 0 范围内的整数键识别。至 k - 1 .它使用 O(n + k)额外的空间。

整数的简单原位变体

此变体要求输入为纯整数，而不是具有整数键的任意对象。它只是从计数数组重建输入数组。

count = array of k zeros
for x in input do
    count[x] += 1

i = 0
for x in 0, 1, ... k - 1 do
    for j in 1, 2, ... count[x] do
        input[i], i = x, i + 1

return input

它使用 O(k)额外的空间。

具有整数键的任意对象的完整原位变体

此变体与常规变体类似地接受任意对象。它使用交换将对象放置在适当的位置。在计算出 count 之后前两个循环中的数组使其保持不变，并使用另一个名为 done 的数组跟踪有多少具有给定键的对象已被放置在正确的位置。

count = array of k+1 zeros
for x in input do
    count[key(x)] += 1

total = 0
for i in 0, 1, ... k do
    count[i], total = total, count[i] + total

done = array of k zeros
for i in 0, 1, ... k - 1 do
    current = count[i] + done[i]
    while done[i] < count[i + 1] - count[i] do
        x = input[current]
        destination = count[key(x)] + done[key(x)]
        if destination = current then
            current += 1
        else
            swap(input[current], input[destination])
        done[key(x)] += 1 

return input

此变体不稳定，因此不能用作基数排序的子例程。它使用 O(2k) = O(k)额外的空间。