用字節比較排序結構的最佳排序算法？

我有一個64個結構的數組，它擁有相當數量的數據（結構大約是128個字節，因此需要重新構建8192個字節）。該數組需要根據每個結構中的單個無符號字節進行排序。我的數據有一個有趣的屬性，它可能會有許多重複的排序值 - 這意味着如果你擺脫了所有重複，數組可能只有10個獨特的元素長，但這不是給定的。用字節比較排序結構的最佳排序算法？

一旦排序，我需要創建一個堆棧來存儲每個唯一的字節運行開始的大小和類型：所以如果我結束了排序的值： 4,4,4,9,9,9， 9,9,14,14 堆棧將是：（4,3），（9,5），（14,2）

我覺得在這些條件下我可以執行一些很好的優化。如果我做了堆排序，我可以在排序時創建棧，但是這會比qsort更快，然後建立棧？由於我使用的大型結構，任何排序算法會運行得慢嗎？我可以做的任何優化，因爲我只比較字節？

順便說一句：語言是C++

謝謝。

來源

2011-01-23 Pubby

你會用什麼做一個堆棧，自制或內置的東西？ – Skurmedel 2011-01-23 17:30:02

我想要最快的，所以我想它會是一個簡單的自制的使用固定緩衝區。 – Pubby 2011-01-23 17:32:37

您是否需要實際排序，或者您是否只需要存儲大小和類型的「堆棧」？ – ThomasMcLeod 2011-01-23 18:32:01

事實上，你的密鑰是整數，並且實際上並不是很多，的概率是Bucket Sort，桶大小爲1，將是非常適用的。

來源

2011-01-23 17:41:59 EvilTeach

我會想象STL會做你想要的。重新編寫自己的排序例程和容器可能很容易出錯，速度也很慢。所以只需要擔心，如果你發現它是一個瓶頸。

來源

2011-01-23 17:42:28

排序不會更慢，因爲您將排序指針或對結構的引用，而不是內存中的實際結構。

來源

2011-01-23 18:29:06 ThomasMcLeod

通常，對於大對象，對對象的指針/索引數組進行排序可能更快，而不是對象。或者對節點數組進行排序，其中每個節點包含對象的指針/索引和對象的排序鍵（在這種情況下，鍵是一個字節）。要在C++中執行此操作，只需向std::sort或std::stable_sort提供合適的比較器即可。然後，如果您需要按順序排列原始對象，而不是隻需要知道正確的順序，最後將對象複製到新的數組中。

複製128個字節幾乎可以肯定比執行字節比較要慢得多，即使是額外的間接尋址。因此，爲了獲得最佳表現，這是您需要查看的動作，而不是比較，指針交易是避免大部分動作的一種方式。

當您在最後執行復制時，您可以構建您的遊程編碼。

當然，使用一些自定義的排序算法可以更快地實現這種算法，該算法可以特殊使用數字（64，「128」和1）。但即使是簡單的問題，例如「最快 - 內插，堆排序或合併排序」，如果不編寫和運行代碼，通常也是不可能的。

來源

2011-01-23 18:36:03

用字節比較排序結構的最佳排序算法？

回答

相關問題