在线性时间和恒定空间中排序前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. 完成