對索引進行排序效率高嗎

所以我想到了一種新的排序算法，它可能很高效，但我對此不太確定。對索引進行排序效率高嗎

1）想象一下，我們有一個只有正數的數組。
2）我們通過數組並找到最大的數字n。
3）我們創建一個大小爲n + 1的新數組b。
4）我們遍歷未排序數組中的每個條目，並在我們正在查看的未排序數組的索引處增加第二個數組中的值。（在僞代碼中，這意味着：b [a [i]] ++;而a [i]是我們目前正在查看的數字）
5）一旦我們完成了a中的每個元素，數組b在每個索引處存儲此索引的確切數量。（例如：b [0] = 3表示我們在初始數組中有3個零點a）
6）我們遍歷整個數組b並跳過所有空字段並從中創建一個新的List或數組。

所以我可以想象，這個算法對於較小的數字可以非常快速有效，因爲最後我們必須通過整個數組b來構建排序的算法，這將會非常耗時。
如果我們例如有一個數組a = {1000,1}，它仍然會檢查數組b中的1001個元素，或者它們是0，儘管我們在初始數組中只有2個元素。
儘管數量較小，但我們幾乎應該得到一個O（n）結果？我不太確定，這就是爲什麼我問你。也許我甚至錯過了一些非常重要的東西。
感謝您的幫助提前:)

來源

2017-09-02 Nick B.

它被稱爲[計數排序]（https://en.wikipedia.org/wiki/Counting_sort）。 –

祝賀您獨立重新發現counting sort。

對於範圍有限的情況，這確實是一種非常好的排序策略，並且項目數量遠遠大於數組中項目的數量。

在範圍大於數組中項目數的情況下，傳統的排序算法會給您更好的性能。這種算法稱爲pseudo-polynomial。

來源

2017-09-02 17:09:03 dasblinkenlight

謝謝你的回答。我很抱歉，但我不知道這個算法已經存在，就像我描述的一樣。 –

我們幾乎應該得到一個O（n）的結果

你得到O（N + M）的結果，當M - 在第一陣列最大數量。另外，你花O（M）記憶，所以它只有在M很小時纔有意義。見counting sort

來源

2017-09-02 17:19:15

對索引進行排序效率高嗎

回答

相關問題