undo nsarray排序

Question

下面是我想用NSArray包含NSNumber的一個例子。

1. 這是我想編輯的NSArray「分數」。
   得分[0] = 30，
   得分[1] = 10，
   得分[2] = 20
   得分[3] = 0
   

2. 按升序順序陣列
   得分[0] = 30 // [0]此數字顯示排序前的索引
   得分[1] = 20 // [2]
   得分[2] = 10 // [1]
   得分[3] ] = 0 // [3]
   

3. 編輯陣列（在這種情況下，第4個給出第1個10分，第3個給出第2個5分）
   得分[0] = 40 // [0]
   得分[1] = 25 // [2]
   得分[2] = 5 // [1]
   得分[3] = - 10 // [3]
   

4. 然後對它們進行排序。
   得分[0] = 40
   得分[1] = 5
   得分[2] = 25
   得分[3] = - 10
   

   我有與列表中的第4號的方法的一個問題有人能給我一些想法嗎？
   在此先感謝。

Answer 1

你實際上並不需要需要來交換這些值本身，你可以設置一個額外的間接級別並使用它。

排序之前，您有索引初始化爲指向相應的分數：

index[0] = 0  score[0] = 30 
index[1] = 1  score[1] = 10 
index[2] = 2  score[2] = 20 
index[3] = 3  score[3] = 0 

排序時，你實際上是指標排序基於它們指向，而不是分數本身的分數。因此，而不是在你的排序如下比較：

if score[i] > score[i+1] then swap score[i], score[i+1] 

你改用：

if score[index[i]] > score[index[i+1]] then swap index[i], index[i+1] 

繼排序，你就必須：

index[0] = 0  score[0] = 30 
index[1] = 2  score[1] = 10 \ These two indexes have been swapped 
index[2] = 1  score[2] = 20 / but NOT the scores. 
index[3] = 3  score[3] = 0 

然後，移動點，您使用間接索引而不是直接值：

score[index[0]] += 10; score[index[3]] -= 10; 
score[index[1]] += 5; score[index[2]] -= 5; 

然後你完全扔掉索引，原來的數組不需要恢復到它原來的順序，只是因爲它的順序從來沒有變過。

Answer 2

做初始化爲這樣一個額外的數組：每次你的排序算法交換兩個指數在score時間

index[0] = 0 
index[1] = 1 
index[2] = 2 
: 

而且，你還交換同一指標在index。

如果你的排序算法是內置的，所以你無法控制它，你將不得不用一個元組（一個對象，一個雙元素數組，無論哪一個更容易在objective-c ），其中on元素是分數，另一個元素是它的原始索引。在排序時，您可以將自定義比較器傳遞給排序函數，以便僅將得分用於比較。這將對您的分數索引元組進行排序，以便您可以使用索引將它們恢復到原始順序。

Answer 3

[代碼將被輸入，檢查它！]

我假設你score陣列實際上是可變的，你打算改變它：

NSMutableArray *score = ...; 

創建另一個陣列相同的大小和初始化到0..N：

NSMutableArray *indices = [NSMutableArray arrayWithCapacity:[score count]]; 
// add the numbers 0..[score count] to indices 

現在使用自定義的比較器中查找012 indices數組進行排序陣列：

[indices sortUsingComparator:(NSComparator)^(NSNumber *a, NSNumber *b) 
{ 
    return [((NSNumber *)[[score objectAtIndex:[a integerValue]]) 
      compare:[[score objectAtIndex:[b integerValue]] 
      ]; 
} 
] 

現在你可以通過索引陣列，例如修改原始數組修改「4」元素源後：

[score replaceObjectAtIndex:[[indices objectAtIndex:3] integerValue] withObject:...]; 

現在你不需要「取消排序」 score可言，你的第4步是「什麼也不做」。