在跟踪索引 C# 的同时快速排序数据数组

Question

我在整数数组上使用快速排序算法有点卡住了，同时在排序过程中保存元素的原始索引，因为它们在移动过程中四处移动。使用 C#/Visual studio 例如

排序数组{52,05,08,66,02,10} 索引：0 1 2 3 4 5

AfterSort 数组 {02,05,08,10,52,66} 索引：4 1 2 5 0 3

我需要将排序值的索引保存在另一个数组中。我觉得这非常复杂，因为快速排序是递归的，任何帮助或指示将不胜感激！谢谢！

Answer 1

正如@Will 所说，您可以这样做：

var myArray = new int[] { 52, 05, 08, 66, 02, 10 };

///In tupple item1 you have the number, in the item2 you have the index  
var myIndexedArray = myArray.Select( ( n, index ) => Tuple.Create( n, index ) );

///Or if you are using c# 7, you can use the tuple literals ! :
var myIndexedArray = myArray.Select( ( n, index ) => ( n, index ) );

///Call your quick sort method, sort by the item1 (the number) inside the method
// or use Enumerable.OrderBy:
myIndexedArray = myIndexedArray.OrderBy(x => x.Item1);

///Then get your things back
int[] numbers = myIndexedArray.Select(x => x.Item1).ToArray();
int[] indexes = myIndexedArray.Select(x => x.Item2).ToArray();

Answer 2

LINQ OrderBy uses QuickSort internally。因此，与其自己实施 QuickSort，不如使用 OrderBy，如果需要，可以使用自定义 IComparer<T>.

将要排序的数据放入一个能记住原始index的匿名类型，然后按value排序。您可以从已排序元素的 index 属性中检索原始索引。

using System.Linq;

var data = new int[] { 52,05,08,66,02,10 };

var sortingDictionary = data
    .Select((value, index) => new { value, index });

var sorted = sortingDictionary
    .OrderBy(kvp => kvp.value)
    .ToList(); // enumerate before looping over result!

for (var newIndex = 0; newIndex < sorted.Count(); newIndex ++) {
    var item = sorted.ElementAt(newIndex);
    Console.WriteLine(
        $"New index: {newIndex}, old index: {item.index}, value: {item.value}"
    );
}

Fiddle

编辑：合并了 mjwills

建议的改进

在跟踪索引 C# 的同时快速排序数据数组

Quick sorting a data array while tracking index C#

c#

arrays

sorting

quicksort

visual-studio