在跟踪索引C时快速排序数据数组＃

我在整数数组上使用快速排序算法时遇到了一些问题，同时在排序过程中移动元素时保存了元素的原始索引。使用C＃/视觉工作室例如在跟踪索引C时快速排序数据数组＃

ToSort阵列{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

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

2017-07-27 AjaxNash

裹在包含索引和数目的对象的整数建议。然后快速排序。之后，您可以迭代列表以检索值和原始索引。贵族。 – Will

正如@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();

来源

2017-07-27 12:51:55 Lucas

谢谢卢卡斯，我会试试看！ – AjaxNash

LINQ OrderByuses 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

来源

2017-07-27 12:59:43

谢谢你，我在答案中加入了改进。 –

谢谢格奥尔格，这也适用！ – AjaxNash

在跟踪索引C时快速排序数据数组＃

回答

相关问题