快速将已知的排序顺序（旧索引 -> 新索引映射）应用于数组

Question

我正在尝试对需要“串联”排序 8 个大型数组的例程进行性能调整，其中一个数组是要排序的数组。

我已经使用我选择的方法对第一个数组进行了排序（我正在使用 TimSort）
我已经确保我的排序对象数组有一个属性表示它们的原始索引。（例如 sortedArray[0].OriginalIndex 将 return 2983 如果之前 unsortedArry[2983] 结果是第一项）

这意味着如果我要遍历我现在排序的对象数组，我想我可以通过以下天真的方式让所有其他数组按相同的顺序排序：

private List<object[]> SortInTandem(IndexedObj[] sortedArray, List<object[]> arraysToSort)
    for(int i = 0; i < sortedArray.length; i++) {
       int originalIndex = sortedArray[i].OriginalIndex;
       // Swap the corresponding index from all other arrays to their new position
       foreach(object[] array in arraysToSort) {
          object temp = array[i];
          array[i] = array[originalIndex];
          array[originalIndex] = temp;
       }
    }
    return arraysToSort; // Returning original arrays sorted in-place
}

我相信上述算法可以得到预期的结果，但感觉效率低于预期。（作业数量是需要的 3 倍？）

我还考虑了以下最小化分配的方法，但需要分配新数组来存储排序的项目，并垃圾收集旧数组（除非我想出一种在调用之间回收分配的方法）：

private List<object[]> SortInTandem(IndexedObj[] sortedArray, List<object[]> arraysToSort) =>
    arraysToSort.Select(array =>
    {
       object[] tandemArray = new object[array.length];   
       for(int i = 0; i < sortedArray.length; i++)
          tandemArray[i] = array[sortedArray[i].OriginalIndex];
    }); // Returning newly-allocated arrays

这种事情是在代码的性能关键区域连续完成的，所以我正在寻找关于如何两全其美的想法。

Answer 1

更多地考虑上面的第二个解决方案（分配新数组）——我想到传入的数组列表也可以在生成排序后的变体后“重新调整用途”，所以我实际上只需要分配一个新数组，然后我可以重用传入的数组来准备其他结果：

// Note the allocated arraysToSort passed in will be repurposed to produced a new set of sorted
// arrays, so the caller must be sure to discard their references and only use what is returned.
private List<object[]> SortInTandem(IndexedObj[] sortedArray, List<object[]> arraysToSort)
{
    List<object[]> sortedArrays = new List<object[]>(arraysToSort.Count);
    object[] tandemArray = new object[array.length];
    for(int i = 0; i < arraysToSort.Count; i++)
    {  
       for(int j = 0; j < sortedArray.length; j++)
          tandemArray[j] = array[sortedArray[j].OriginalIndex];
       sortedArrays.Add(tandemArray);
       tandemArray = arraysToSort[i];
    }
    return sortedArrays; // Returning one newly-allocated + all but one original arrays repurposed
}

快速将已知的排序顺序（旧索引 -> 新索引映射）应用于数组

Quickly apply a known sort order (old index -> new index mapping) to an array

c#

arrays

sorting

algorithm

performance