0

i was wondering, when i have a list of integers and i need to sort them, and i know that they are integers in 32 bit, can i use radix sort (with counting sort as its stable sort) to sort them in o(n) time?

isn't it just 32 counting sorts using the bits representation on the numbers starting from LSB?

i know that general sorts with no previous knowledge of the numbers take o(nlogn), but isnt the fact that they are 32 bit integers is all i need to make it an o(n) sort?

thanks!

4

1 回答 1

0

是的！基数排序适用于无符号整数，也适用于有符号整数（需要做更多工作）。

有趣的是，如果它们的位被重新解释为整数，它也适用于非 NaN、非负浮点数。（负浮点数需要更多的工作，而且可能不值得。）

于 2014-01-01T19:49:12.007 回答