在給定存儲空間O（n）的情況下，可以將n個元素排序到範圍{1,2，... n^2）中多快？

我正在考慮使用計數排序。但我不認爲這是答案，因爲在這種情況下，k是n^2。所以排序時間是O（n + n^2）。另外我認爲這將超過存儲限制。在給定存儲空間O（n）的情況下，可以將n個元素排序到範圍{1,2，... n^2）中多快？

任何想法？

謝謝。

2011-12-31 spider

您拍照時看一下[快速排序（ http://en.wikipedia.org/wiki/Quicksort）？ – Makoto 2011-12-31 00:42:50

@Makoto：當你拿起一個壞支點的快速排序，運行時間將是爲O（n^2）。此外，我給了O（n）的存儲空間，所以我認爲我可以使用需要一些空間的排序算法。 – spider 2011-12-31 00:58:58

也許我誤解，但這似乎是一個兩位數基 - 正基數排序因此這是O（n）。在[i]％n上的第一次傳球，第二次傳球在[i]/n上投籃。這需要O（n）輔助存儲。 – 2011-12-31 01:03:29

可以使用bottom-up merge sort實現這一目標，它運行在爲O（n log n）的，無需額外的空間（因爲它是就地）。

2011-12-31 00:48:40

嗯，以分鐘打我:) – BlackBear 2011-12-31 00:52:26

，使其將列表分成n個部分，而不是半可以使用Merge Sort略加修改的版本。合併排序的時間複雜度爲O（n log n），但我不知道如何獲得編輯版本的時間複雜度。
如果有人可以幫助我，我將它添加到我的答案:)

編輯：
它似乎已經有人發明了這個，看看@ JSPerfUnkn0wn的答案

2011-12-31 00:51:37 BlackBear

回答