是否有线性时间复杂度和O(1)
辅助空间复杂度的排序算法来对正整数列表进行排序?我知道radix sort和 counting sort具有线性时间复杂度(O(kn)
和 O(n+k)
,如果我们将 k
视为常量),但它们都具有 O(n+k)
辅助空间复杂度。一种类型甚至有可能同时具有这两个属性吗?我们将不胜感激。
最佳答案
如果我们只对整数进行排序,我们可以使用计数排序的原位变体,它具有 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)
额外的空间。
关于algorithm - 有线性时间复杂度O(1)辅助空间复杂度的排序算法吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/63561965/