有线性时间复杂度O(1)辅助space复杂度的排序算法吗？
Is there a sorting algorithm with linear time complexity and O(1) auxiliary space complexity?
是否有线性时间复杂度和O(1)辅助space复杂度的排序算法来对正整数列表进行排序？我知道 radix sort and counting sort 具有线性时间复杂度（如果我们以 k 为常量，则分别为 O(kn) 和 O(n+k)），但它们都有 O(n+k) 辅助 space 复杂性。一种类型甚至有可能同时具有这两个属性吗？我们将不胜感激。
如果我们只对整数进行排序，我们可以使用 in-situ 计数排序的变体，它具有 O(k) space 复杂度，它独立于变量 n .换句话说，当我们将 k 视为常量时，space 的复杂度为 O(1).
或者，我们可以使用 in place radix sort 和具有 O(lg k) space 复杂度（由于递归）的二进制分区的 lg k 阶段。甚至更少的阶段使用计数排序来确定 n-way 分区的桶边界。这些解决方案的时间复杂度为 O(lg k * n)，当仅用变量 n 表示时，时间复杂度为 O(n)（当 k 被视为常量时）。
获得O(n)步复杂度和O(1)space复杂度的另一种可能方法，当k被认为是常数时，是使用可以称为减法排序的东西，正如 OP 在 , or elsewhere 中所描述的那样。它具有比 O(kn) 更好的步骤复杂度 O(sum(input))（并且对于某些特定输入，它甚至比 binary-radix 排序的 O(lg k * n) 更好，例如，对于 [=] 形式的所有输入29=]) 和 space 复杂度 O(1).
另一种解决方案是使用 bingo sort，它具有步长复杂度 O(vn)，其中 v <= k 是输入中唯一值的数量，space 复杂度 O(1).
请注意，这两种排序解决方案都不稳定，如果我们对不仅仅是整数（一些带有整数键的任意对象）进行排序时，这一点很重要。
在此 paper 中还描述了一种尖端的稳定分区算法，具有 O(1) space 的复杂性。结合基数排序，可以构造一个稳定的线性排序算法，其步复杂度为space - O(lg k * n)，复杂度为O(1) space。
编辑：
根据评论的要求，我试图找到计数排序的“in-situ”变体的来源，但没有找到我能找到的质量好的东西link 到（对于这样一个基本算法没有容易获得的描述真的很奇怪）。因此，我在这里发布算法：
常规计数排序（来自维基百科）
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) 额外的 space.
整数的简单 in-situ 变体
此变体要求输入为纯整数，而不是具有整数键的任意对象。它只是从计数数组重建输入数组。
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) 额外的 space。
具有整数键的任意对象的完整 in-situ 变体
此变体与常规变体类似地接受任意对象。它使用交换将对象放置在适当的位置。在前两个循环中计算 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) 额外的 space.
这里是一个排序算法，时间复杂度为线性，辅助space复杂度为O(1)。我称之为 subtract-sort。这是 C 中的代码（可运行here）。
// Subtract Sort
#include<stdio.h>
int print_arr(int arr[], int n)
{
int z;
for(z=0 ; z<n ; z++)
{
printf("%d ", arr[z]);
}
}
void subtract_sort(int arr[], int arr_size)
{
int j=0;
int val=1;
int all_zero=0;
while(!all_zero)
{
int m;
all_zero=1;
int i;
for(i=j ; i<arr_size ; i++)
{
arr[i]--;
if(arr[i]==0)
{
arr[i]=arr[j];
arr[j]=val;
j++;
}
all_zero=0;
}
val++;
}
}
int main()
{
int arr[12]={2,10,3,7,9,8,54,3,9,38,8};
int size=11;
subtract_sort(arr, size);
printf("\n--------------------------\n");
print_arr(arr, size);
return 0;
}
该算法的 worst-case 时间复杂度为 O(kn)，其中 k 是数组的最大元素。该算法对于包含小值的大数组是有效的（优于快速排序），但对于包含大值的小数组非常低效。时间复杂度也正好等于sum(arr)，也就是数组中所有元素的总和。
对于那些说这个算法没有线性时间的人，给我找一个超过我计算的 worst-case 时间复杂度 O(kn) 的数组。如果找到这样的反例，我会很高兴地同意你的看法。
worst-case 场景的 this example 可能有助于理解时间复杂度。
再举一个排序算法的例子，时间复杂度为线性（如果k为常量），O(1)辅助space复杂度，也很稳定。这是我写的用户 ciamej 在他的回答中提到的“二进制基数排序”的实现。我无法在互联网上找到满足所有 3 个属性的该算法的任何实现，这就是为什么我觉得将它添加到这里是个好主意。你可以试试here.
// Binary Radix Sort
#include<stdio.h>
#include<math.h>
int print_arr(int arr[], int n)
{
int z;
for(z=0 ; z<n ; z++)
{
printf("%d ", arr[z]);
}
printf("\n");
}
int getMax(int arr[], int n)
{
int mx = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > mx)
mx = arr[i];
return mx;
}
void BinaryRadixSort(int arr[], int arr_size)
{
int biggest_int_len = log2(getMax(arr, arr_size))+1;
int i;
int digit;
for(i=1 ; i<=biggest_int_len ; i++)
{
digit=i;
int j;
int bit;
int pos=0;
int min=-1;
int min2=-1;
int min_val;
for(j=0 ; j<arr_size ; j++)
{
int len=(int) (log2(arr[j])+1);
if(i>len)
{
bit=0;
}
else
{
bit=(arr[j] & (1 << (digit - 1)));
}
if(bit==0)
{
min_val=arr[j];
min=j;
min2=j;
break;
}
}
while(min!=-1)
{
while(min>pos)
{
arr[min]=arr[min-1];
min--;
}
arr[pos]=min_val;
pos++;
int k;
min=-1;
for(k=min2+1 ; k<arr_size ; k++)
{
int len=(int) (log2(arr[k])+1);
if(i>len)
{
bit=0;
}
else
{
bit= arr[k] & (1 << (digit-1));
}
if(bit==0)
{
min_val=arr[k];
min=k;
min2=k;
break;
}
}
}
}
}
int main()
{
int arr[16]={10,43,73,14,64,2,6,1,5,3,6,3,5,8,4,5};
int size=16;
BinaryRadixSort(arr, size);
printf("\n--------------------------\n");
print_arr(arr, size);
return 0;
}
这个算法的时间复杂度是O(log2(k).n)，其中k是列表中最大的数，n是列表中元素的个数。
我想在这里包括一个算法，它是对 Mathphile 第一个答案的改进。在那种情况下，想法是将输入的未排序后缀中的每个数字剃掉 1（同时将已排序的数字交换到前缀中）。每当未排序后缀中的数字达到 0 时，就意味着它小于未排序后缀中的任何其他数字（因为所有数字都以相同的速率减少）。
有一个可能的重大改进：在不改变时间复杂度的情况下，我们可以减去比 1 大得多的数字 - 事实上，我们可以减去等于最小的剩余未排序项目的数字。这使得这种排序可以很好地运行，而不管数组项的数字大小，以及浮点值！ javascript 实现：
let subtractSort = arr => {
let sortedLen = 0;
let lastMin = 0; // Could also be `Math.min(...arr)`
let total = 0;
while (sortedLen < arr.length) {
let min = arr[sortedLen];
for (let i = sortedLen; i < arr.length; i++) {
if (arr[i]) {
arr[i] -= lastMin;
if (arr[i]) min = Math.min(min, arr[i]);
} else {
arr[i] = arr[sortedLen];
arr[sortedLen] = total;
sortedLen++;
}
}
total += lastMin;
lastMin = min;
}
return arr;
};
let examples = [
[ 3, 2, 5, 4, 8, 5, 7, 1 ],
[ 3000, 2000, 5000, 4000, 8000, 5000, 7000, 1000 ],
[ 0.3, 0.2, 0.5, 0.4, 0.8, 0.5, 0.7, 0.1 ],
[ 26573726573, 678687, 3490, 465684586 ]
];
for (let example of examples) {
console.log(`Unsorted: ${example.join(', ')}`);
console.log(`Sorted: ${subtractSort(example).join(', ')}`);
console.log('');
}
请注意，这种排序仅适用于正数。要使用负数，我们需要找到最负的项目，从数组中的每个项目中减去这个负值，对数组进行排序，最后将最负的值添加回每个项目——总的来说，这不会增加时间复杂度.
是否有线性时间复杂度和O(1)辅助space复杂度的排序算法来对正整数列表进行排序？我知道 radix sort and counting sort 具有线性时间复杂度（如果我们以 k 为常量，则分别为 O(kn) 和 O(n+k)），但它们都有 O(n+k) 辅助 space 复杂性。一种类型甚至有可能同时具有这两个属性吗？我们将不胜感激。
如果我们只对整数进行排序，我们可以使用 in-situ 计数排序的变体，它具有 O(k) space 复杂度，它独立于变量 n .换句话说，当我们将 k 视为常量时，space 的复杂度为 O(1).
或者，我们可以使用 in place radix sort 和具有 O(lg k) space 复杂度（由于递归）的二进制分区的 lg k 阶段。甚至更少的阶段使用计数排序来确定 n-way 分区的桶边界。这些解决方案的时间复杂度为 O(lg k * n)，当仅用变量 n 表示时，时间复杂度为 O(n)（当 k 被视为常量时）。
获得O(n)步复杂度和O(1)space复杂度的另一种可能方法，当k被认为是常数时，是使用可以称为减法排序的东西，正如 OP 在 O(kn) 更好的步骤复杂度 O(sum(input))（并且对于某些特定输入，它甚至比 binary-radix 排序的 O(lg k * n) 更好，例如，对于 [=] 形式的所有输入29=]) 和 space 复杂度 O(1).
另一种解决方案是使用 bingo sort，它具有步长复杂度 O(vn)，其中 v <= k 是输入中唯一值的数量，space 复杂度 O(1).
请注意，这两种排序解决方案都不稳定，如果我们对不仅仅是整数（一些带有整数键的任意对象）进行排序时，这一点很重要。
在此 paper 中还描述了一种尖端的稳定分区算法，具有 O(1) space 的复杂性。结合基数排序，可以构造一个稳定的线性排序算法，其步复杂度为space - O(lg k * n)，复杂度为O(1) space。
编辑：
根据评论的要求，我试图找到计数排序的“in-situ”变体的来源，但没有找到我能找到的质量好的东西link 到（对于这样一个基本算法没有容易获得的描述真的很奇怪）。因此，我在这里发布算法：
常规计数排序（来自维基百科）
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) 额外的 space.
整数的简单 in-situ 变体
此变体要求输入为纯整数，而不是具有整数键的任意对象。它只是从计数数组重建输入数组。
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) 额外的 space。
具有整数键的任意对象的完整 in-situ 变体
此变体与常规变体类似地接受任意对象。它使用交换将对象放置在适当的位置。在前两个循环中计算 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) 额外的 space.
这里是一个排序算法，时间复杂度为线性，辅助space复杂度为O(1)。我称之为 subtract-sort。这是 C 中的代码（可运行here）。
// Subtract Sort
#include<stdio.h>
int print_arr(int arr[], int n)
{
int z;
for(z=0 ; z<n ; z++)
{
printf("%d ", arr[z]);
}
}
void subtract_sort(int arr[], int arr_size)
{
int j=0;
int val=1;
int all_zero=0;
while(!all_zero)
{
int m;
all_zero=1;
int i;
for(i=j ; i<arr_size ; i++)
{
arr[i]--;
if(arr[i]==0)
{
arr[i]=arr[j];
arr[j]=val;
j++;
}
all_zero=0;
}
val++;
}
}
int main()
{
int arr[12]={2,10,3,7,9,8,54,3,9,38,8};
int size=11;
subtract_sort(arr, size);
printf("\n--------------------------\n");
print_arr(arr, size);
return 0;
}
该算法的 worst-case 时间复杂度为 O(kn)，其中 k 是数组的最大元素。该算法对于包含小值的大数组是有效的（优于快速排序），但对于包含大值的小数组非常低效。时间复杂度也正好等于sum(arr)，也就是数组中所有元素的总和。
对于那些说这个算法没有线性时间的人，给我找一个超过我计算的 worst-case 时间复杂度 O(kn) 的数组。如果找到这样的反例，我会很高兴地同意你的看法。
worst-case 场景的 this example 可能有助于理解时间复杂度。
再举一个排序算法的例子，时间复杂度为线性（如果k为常量），O(1)辅助space复杂度，也很稳定。这是我写的用户 ciamej 在他的回答中提到的“二进制基数排序”的实现。我无法在互联网上找到满足所有 3 个属性的该算法的任何实现，这就是为什么我觉得将它添加到这里是个好主意。你可以试试here.
// Binary Radix Sort
#include<stdio.h>
#include<math.h>
int print_arr(int arr[], int n)
{
int z;
for(z=0 ; z<n ; z++)
{
printf("%d ", arr[z]);
}
printf("\n");
}
int getMax(int arr[], int n)
{
int mx = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > mx)
mx = arr[i];
return mx;
}
void BinaryRadixSort(int arr[], int arr_size)
{
int biggest_int_len = log2(getMax(arr, arr_size))+1;
int i;
int digit;
for(i=1 ; i<=biggest_int_len ; i++)
{
digit=i;
int j;
int bit;
int pos=0;
int min=-1;
int min2=-1;
int min_val;
for(j=0 ; j<arr_size ; j++)
{
int len=(int) (log2(arr[j])+1);
if(i>len)
{
bit=0;
}
else
{
bit=(arr[j] & (1 << (digit - 1)));
}
if(bit==0)
{
min_val=arr[j];
min=j;
min2=j;
break;
}
}
while(min!=-1)
{
while(min>pos)
{
arr[min]=arr[min-1];
min--;
}
arr[pos]=min_val;
pos++;
int k;
min=-1;
for(k=min2+1 ; k<arr_size ; k++)
{
int len=(int) (log2(arr[k])+1);
if(i>len)
{
bit=0;
}
else
{
bit= arr[k] & (1 << (digit-1));
}
if(bit==0)
{
min_val=arr[k];
min=k;
min2=k;
break;
}
}
}
}
}
int main()
{
int arr[16]={10,43,73,14,64,2,6,1,5,3,6,3,5,8,4,5};
int size=16;
BinaryRadixSort(arr, size);
printf("\n--------------------------\n");
print_arr(arr, size);
return 0;
}
这个算法的时间复杂度是O(log2(k).n)，其中k是列表中最大的数，n是列表中元素的个数。
我想在这里包括一个算法，它是对 Mathphile 第一个答案的改进。在那种情况下，想法是将输入的未排序后缀中的每个数字剃掉 1（同时将已排序的数字交换到前缀中）。每当未排序后缀中的数字达到 0 时，就意味着它小于未排序后缀中的任何其他数字（因为所有数字都以相同的速率减少）。
有一个可能的重大改进：在不改变时间复杂度的情况下，我们可以减去比 1 大得多的数字 - 事实上，我们可以减去等于最小的剩余未排序项目的数字。这使得这种排序可以很好地运行，而不管数组项的数字大小，以及浮点值！ javascript 实现：
let subtractSort = arr => {
let sortedLen = 0;
let lastMin = 0; // Could also be `Math.min(...arr)`
let total = 0;
while (sortedLen < arr.length) {
let min = arr[sortedLen];
for (let i = sortedLen; i < arr.length; i++) {
if (arr[i]) {
arr[i] -= lastMin;
if (arr[i]) min = Math.min(min, arr[i]);
} else {
arr[i] = arr[sortedLen];
arr[sortedLen] = total;
sortedLen++;
}
}
total += lastMin;
lastMin = min;
}
return arr;
};
let examples = [
[ 3, 2, 5, 4, 8, 5, 7, 1 ],
[ 3000, 2000, 5000, 4000, 8000, 5000, 7000, 1000 ],
[ 0.3, 0.2, 0.5, 0.4, 0.8, 0.5, 0.7, 0.1 ],
[ 26573726573, 678687, 3490, 465684586 ]
];
for (let example of examples) {
console.log(`Unsorted: ${example.join(', ')}`);
console.log(`Sorted: ${subtractSort(example).join(', ')}`);
console.log('');
}
请注意，这种排序仅适用于正数。要使用负数，我们需要找到最负的项目，从数组中的每个项目中减去这个负值，对数组进行排序，最后将最负的值添加回每个项目——总的来说，这不会增加时间复杂度.