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步是“什么也不做”。