位排序的空间复杂度是什么？

Question

位排序的空间复杂度是什么？根据最佳和平均情况，其为O（n）。我想知道它的空间复杂度是什么

来源标题：位排序：排序新技术

IEEE研究仅关注时间复杂度。

谢谢！

Answer 1

它的O(n)，因为您没有创建任何新元素（理论上），所以您没有任何深层副本。只需检查它的位表示形式并交换位置即可。所以基本上，在那些步骤中：

Step 1: convert all elements into binary form but converted elements are in same BIT
sequence form.
Step 2: find elements whose first leftmost bit is 1
Step 3: repeat step 2 to all selected elements until get single BIT sequence number
Step 4: swap selected BIT sequence with last element of an array
Step 5: repeat step2, step3 and step4 until all elements are sorted
Step 6: convert sorted BIT sequence elements into decimal number

理论上，您没有任何新元素。但是，如果确实要实现以位表示形式创建给定元素的深层副本，然后再次将其转换回元素，则其仍为O(n)（只是3*n）。