在跟蹤索引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時快速排序數據數組＃

回答

相關問題