Mat*_*ile 2 sorting algorithm time-complexity space-complexity
是否有线性时间复杂度和O(1)辅助空间复杂度的排序算法来对正整数列表进行排序？我知道，基数分类和计数排序具有线性时间复杂度（O(kn)和O(n+k)分别，如果我们采取k恒定），但它们都有O(n+k)辅助空间复杂度。甚至有可能同时拥有这两种属性吗？此类示例将不胜感激。
如果我们只对整数进行排序，我们可以使用计数排序的原位变体，它具有O(k)空间复杂度，独立于变量n。换句话说，当我们将其k视为常数时，空间复杂度为O(1)。
或者，我们可以使用替代基数排序与lg k二进制分区的相位O(lg k)空间复杂度（由于递归）。或者甚至更少的阶段，使用计数排序来确定 n 路分区的桶边界。这些解决方案的时间复杂度为O(lg k * n)，当仅用变量n表示O(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)额外的空间。