c - 什么算法可以在线性时间内对新值和重复值进行排序，而不使用额外的空间？

Question

[7,1,2,3,2,4,1,5,6]

什么算法可以在线性时间内对新值和重复值进行排序，而不使用额外的空间？

据我所知，计数排序对唯一值进行排序，其他比较排序都不是 O(n)。

Answer 1

你的问题并不是很恰当，因为计数排序的问题不在于它不对重复值进行排序(它对它们进行很好的排序，这就是为什么它是“计数排序”而不是“标志设置排序” ")，而是(正如 babon 上面指出的那样)计数排序至少需要 O(k) 额外空间，其中 k 是数组中不同值的数量.

但是先把这个放在一边。 。 。如果这些是有限大小的整数(例如 32 位整数)，您可以使用 American flag sort ，它是基数排序的就地变体。假设您想要最少的额外空间(您说“没有额外空间”，但这是不可能的，因为即使单个索引变量 i 也构成“额外空间”)，您可以按如下方式进行:

• 首先，将小于0的元素划分在大于或等于0的元素之前。 (您可以按照与 segregate even and odd numbers 相同的方式执行此操作，只不过使用 & 0x8000 而不是 % 2。)
• 接下来，在第一个(小于 0)分区中，将小于 0xC000 的元素划分在大于或等于它的元素之前;在第二个(大于或等于0)分区中，将小于0x4000的元素划分在大于或等于的元素之前到0x4000。 (您可以使用与上一步相同的方法，只不过您还需要留意何时从一个分区转换到另一个分区。)
• 并且，对于每个后续位也是如此。

总的来说，这涉及到数组的 32 次传递(如果这些是 32 位整数)，所以它的时间复杂度为 O(32n) = O(n)。