對O（n）中的數組進行排序

Question

假設您有n個整數，範圍從0到n^3-1。有沒有什麼辦法可以在O（n）時間對它們進行分類？我得到了Uni的這個問題，據我所知，只能使用mergesort或quicksort在NlogN中搜索它們，所以我懷疑這是一個詭計的問題。我還想知道爲什麼給出了（0，n^3-1）的特定範圍？它有什麼特別的特徵嗎？我也在考慮使用Counting Sort來做它們，但據我所知，它運行在O（n + k）時間內，而不是O（n）。請幫忙！

Answer 1

使用「計數排序」，您可以在O（n）中的最後n位以穩定的方式對項進行排序。然後你可以在中間位上排序，然後在最高位上排序。因爲密鑰小於n^3 - 1，所以計數排序的數量是固定的（三個），而O（n）的三倍仍然是O（n）。