algorithm - 在线性时间和常数空间中对前 n 个整数进行排序

Question

我正在寻找一种非比较或基于比较的算法，该算法可以对包含前 n 个正整数的任意排列的数组进行排序，这应该是 O(n) 时间复杂度和 O(1) 空间复杂度。

是否有符合这些规范的现有算法？

Answer 1

如果你有一个大小为 N 的数组，其中包含从 1 到 N 的所有整数，你可以使用以下 O(N) 算法(注意:为了不引入不必要的复杂性，为了这个伪代码，数组是基于 1 的在解释算法时):

1. 从第一个数组元素开始。
   
2. 如果它的数组索引匹配它的值，转到下一个。
   
3. 如果不是，则将其与该值对应的数组索引处的值进行交换。
   
4. 重复第 3 步，直到不再需要交换为止。
   
5. 如果不在数组末尾，则转到下一个数组元素，否则转到第7步
   
6. 转到第 2 步。
   
7. 完成