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

如果我们只对整数进行排序，我们可以使用具有空间复杂度的计数排序的原位变体O(k)，它与变量无关n。换句话说，当我们将k其视为常数时，空间复杂度为O(1)。

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

当被认为是恒定的时，获得O(n)步长复杂度和O(1)空间复杂度的另一种可能方法k是使用可以称为减法排序的东西，如 OP 在他们自己的答案或其他地方所描述的那样。它的步长复杂度O(sum(input))优于O(kn)（对于某些特定的输入，它甚至比二进制基数排序更好O(lg k * n)，例如对于表单的所有输入[k, 0, 0, ... 0]）和空间复杂度O(1)。

另一个解决方案是使用具有步长复杂度的宾果排序O(vn)，其中v <= k输入中唯一值的数量和空间复杂度为O(1)。

请注意，这些排序解决方案都不是稳定的，如果我们排序的不仅仅是整数（一些具有整数键的任意对象），这很重要。

本文还描述了一种具有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)额外的空间。

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

问题描述

解决方案

编辑：

推荐阅读