ios - 如何根据对象在 objective-c 中另一个数组中的顺序对一个数组进行排序？

Question

我有按用户排序的列表。然后我再次从服务器获取列表。
某些元素可能会被删除或添加。我想根据前一个数组的排序对新数组进行排序，然后添加新元素。

示例
oldElementList: [1, 4, 2, 8] ---> 用户设置此顺序
新元素列表:[1,4,3,8]

我想要的输出是:[1, 4, 8, 3]

实际上元素不是数字，它们是对象。当它们从服务器获取时，它们的一些属性值可能已经改变。

我的回答:

for (ElementModel *oldElement in oldElementList) {
            for (ElementModel * newElement in newElementList) {
                if ([newElement.number isEqualToString: oldElement.number]) {
                    [sortedArray addObject: newElement];
                    [newElementList removeObject: newElement];

                    break;
                }
            }
        }

        for (ElementModel *newElement in newElementList) {
            [sortedArray addObject: newElement];
        }

我觉得我的回答不好，我想在性能上或者其他任何我没有考虑到的方面做得更好。

Answer 1

哪种排序算法合适很大程度上取决于您的数据，例如:
- 要排序的数据集是否很大(只有这样，复杂的算法才能发挥作用)？
- 数据集的排序是完全随机的还是预排序的？
从你的描述来看，在我看来，你有一个很大的数据集(否则任何给出正确结果的算法都可能没问题，包括你自己的复杂度为 O(n^2) 的算法)，并且它是预先排序的，即有只是一些增删改(不然保留原来的排序可能就没那么重要了)。
如果是这样，那么下面的算法怎么样(抱歉，它是用 Swift 编写的，但肯定可以轻松转换为 Obj-C):

let old = [1, 4, 2, 7, 8]
let new = [1, 4, 3, 8, 2]

var oldIndexed: [Int: Int] = [:]
for i in 0 ..< old.count {
    oldIndexed[old[i]] = i
}
var newIndexed: [Int: Int] = [:]
for i in 0 ..< new.count {
    newIndexed[new[i]] = oldIndexed[new[i]] ?? old.count
}
var resultArray: [(Int, Int)] = []
for (key, value) in newIndexed {
    resultArray.append((key, value))
}
resultArray = resultArray.sorted { (first, second) -> Bool in
    first.1 < second.1
}
let result = resultArray.map{ $0.0 } // Here: [1, 4, 2, 8, 3]

这个想法是为旧数据元素提供一个索引，并为每个新数据元素提供相同的索引。这是通过使用字典来完成的，因为每个元素都可以通过其键来访问，时间复杂度为 O(1)。新元素获得更大的索引(这也可以是一个计数器以使其更清晰)。然后新字典被转换回数组，然后按其索引排序。最终，索引被删除，结果就准备好了。
我猜想，该算法的复杂性是由应该是最佳的排序函数决定的，因为它是在标准库中实现的。

编辑:

我已经很长时间没有使用 Obj-C 编程了，但只是为了好玩再次尝试一下:

NSArray *old = @[@1, @4, @2, @7, @8];
NSArray *new = @[@1, @4, @3, @8, @2];

NSMutableDictionary *oldIndexed = [[NSMutableDictionary alloc] init];
for (int i = 0; i < old.count; i++) {
    [oldIndexed setValue:[NSNumber numberWithInt: i] forKey: old[i]];
}

NSMutableDictionary *newIndexed = [[NSMutableDictionary alloc] init];
long counter = old.count;
for (int i = 0; i < old.count; i++) {
    NSNumber *oldIndexOfNewValue = oldIndexed[new[i]];
    NSNumber *newIndex;
    if (oldIndexOfNewValue != nil) {
        newIndex = oldIndexOfNewValue;
    } else {
        newIndex = [NSNumber numberWithLong: counter];
        counter++;
    }
    [newIndexed setValue: newIndex forKey: new[i]];
}

NSMutableArray *resultArray = [[NSMutableArray alloc] init];
NSArray *allKeysInNewIndexed = newIndexed.allKeys;
for (int i = 0; i < allKeysInNewIndexed.count; i++) {
    NSNumber *nextKey = allKeysInNewIndexed[i];
    NSArray *nextPair = @[nextKey, newIndexed[nextKey]];
    [resultArray addObject: nextPair];
}

NSArray *sortedResultArray;
sortedResultArray = [resultArray sortedArrayUsingComparator: ^NSComparisonResult(NSArray *first, NSArray *second) {
    NSNumber *firstIndex = first[1];
    NSNumber *secondIndex = second[1];
    return [firstIndex compare: secondIndex];
}];

NSMutableArray * result = [[NSMutableArray alloc] init];
for (int i = 0; i < sortedResultArray.count; i++) {
    [result addObject: sortedResultArray[i][0]];
}