迭代时排序的最佳算法是什么

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; 
     } 
    } 
}