迭代時排序的最佳算法是什麼

Question

比方說，我有一個數組，並且我想在迭代數組的同時對數組的索引進行排序。數組不會被修改，但索引會根據數組元素的值按排序順序放置。讓我舉一個例子。

陣列= [1，7,5，4，3，8]

的排序索引將是，

SortedIndexes = [0,4，3，2，1,5]

我希望它能夠在迭代整個數組後，我已經有了這些排序好的索引。現在，最好的辦法是做什麼。

Answer 1

您將首先創建一個包含主數組索引的輔助數組，首先按順序。輔助數組就是你實際要分類的東西。

然後，您可以將主陣列上的迭代與輔助數組的插入排序組合在一起。對於主迭代中的每個索引，首先執行您希望進行的主操作的任何處理，然後在輔助數組中執行插入排序的插入步驟。完成後，輔助數組包含已排序的索引。

插入排序是一種比較排序，因此它的平均和最壞情況的成本比例與N ，但它是該類中最好的。它的主要優勢在於它的工作方式可以與您的主要迭代完全整合。如果數據不會很大，那麼擴展可能不是問題。對於較小的數據，Insertion Sort可能實際上超過了一些更好的替代方案。

Answer 2

合併排序可以做更多移動，但比快速排序少。在這種情況下，索引正在移動，並且正在比較對象。事實上，對象的比較開銷涉及一個間接級別（通過索引訪問），並且對象比較通常是隨機分佈的，而不是緩存友好的意味着比較開銷大於索引開銷開銷，在這種情況下合併排序應該快於快速排序。

一旦您有一個排序索引數組，您可以使用循環排序的變化在O（n）時間內對原始數組重新排序。這具有將索引數組恢復爲0到n-1的副作用。

void reorder_according_to(int array[], size_t indices[], size_t len) 
{ 
size_t i, j, k; 
int t; 
    for(i = 0; i < len; i++){ 
     if(i != indices[i]){ 
      t = array[i]; 
      k = i; 
      while(i != (j = indices[k])){ 
       array[k] = array[j]; 
       indices[k] = k; 
       k = j; 
      } 
      array[k] = t; 
      indices[k] = k; 
     } 
    } 
}