如何有效排序有序序列陣列

我正在實現複雜的算法，其中的部分是排序有序數字序列陣列。整個算法應該是nlog（n）複雜度，所以這部分應該相同或更好，但我不知道如何做到這一點。如何有效排序有序序列陣列

有一個例子。有序列的陣列：

(0) 
(0,1) 
(0) 
(0,5) 
(2,4) 
() 
(0,5) 
() 
(2,4) 
(1,3,4)

和最終排序應該是：

() 
() 
(0) 
(0) 
(0,1) 
(0,5) 
(0,5) 
(1,3,4) 
(2,4) 
(2,4)

有一些重要的注意事項：

排序是辭書
序列是有序的，但有不是連續性的保證
也有空seque NCES
有很多相同的序列
序列是從0到幾百長，沒有更多的
陣列可以是100K長，大概沒有更多
最終實現將在C++，但現在它是不可能很重要

你能告訴我如何對它進行分類的最佳方法嗎？非常感謝

來源

2011-02-06 Gaim

如果您的實現將在C++中使用'std :: sort'和'std :: lexicographical_compare'。這會給你想要的複雜性，你可以合理確信代碼將起作用。 – Blastfurnace

@Blastfurnace最後，我使用了'std :: sort'，並感謝你指出'std :: lexicographical_compare'，我不知道它。 – Gaim

如果使用快速排序，那麼排序算法將是O（n log n）。如何比較這兩個項目與排序本身的複雜性無關，並且有其自身的複雜性（大概是O（m））。

來源

2011-02-06 09:57:21 wuputah

爲什麼它不重要？有很多比較，也有很多相同的序列，所以比較將是多次線性的。我想複雜度將是O（m n logn），當m = 100時它是重要的。 – Gaim

即使在m = 100時，它甚至不會與n = 10000時的n * log（n）相比較。排序是主導算法。你的比較運算符只是'strcmp（）'，或者如果數據是以整數形式存儲的話，它就是一個類似strcmp的函數。「琴絃」多久不會產生重大影響。 – wuputah

（+1）指出比較不會影響平均複雜度。 –

如果您可以將GPLv3代碼集成到您的項目中，GNU Sort可能是一個很好的開始。至少，當我在示例輸入中運行它時，我得到了您的示例輸出，因此它不會立即錯誤。

來源

2011-02-06 10:00:18 sarnold

請問有什麼描述，特色和教程？我找不到它。 – Gaim

@Gaim，它是Linux系統中包含的標準'sort（1）'工具; '信息排序'將會產生一堆文件。關於排序本身，「按照Knuth第3卷（第2版），練習5.2.4-23建議的方式，使用遞歸分而治之算法，使用練習5.2.4-10建議的優化;這需要空間只有1.5 * N行，而不是通常的2 * N行。Knuth寫道，這種內存優化最初由DA Bell，Comp J. 1（1958），75發表。 – sarnold

你的問題看起來類似於radix sort，在這種情況下，首先按最右邊的項目（例如第100項）對你的序列進行排序，如果沒有這樣的項目存在，則將其設置爲min possible value - 1（例如，在我能看到-1的情況下）然後用第二個最右邊的項目對這個排序的序列進行排序，然後繼續。

此外，如果序列中的項目都在1..k之間（在這種情況下，我可以看到有1..9之間）使用counting sort在O（n）中對它們進行排序，如果您可以使用計數排序，排序時間爲O（n），但排序時間爲O（n log n）。

來源

2011-02-06 10:20:45

+1基數排序，我知道算法，但我忘了它。也許這是我正在尋找的。我需要一段時間來嘗試 – Gaim

如何有效排序有序序列陣列

回答

相關問題