0

我有两个排序 NSMutableArrays（或者我可以使用任何其他集合，不是关键的），我需要将对象从第一个数组插入到第二个数组中，并在第二个数组中保留排序顺序。做到这一点的最佳（最快）方法是什么？我可以实现所有已知的好算法，但我的问题是，是否已经有一些内置方法？如果不是，在我的情况下最好的算法是什么？

4

5 回答 5

3

真正的答案是：这取决于您，因为您在问：在保持排序顺序的同时将对象从一个数组插入另一个数组的最快方法是什么。

没有内置的插入排序数组的正确位置的方法。只需将两个数组相加即可达到相同的效果，但这不是“最快的方法”。

实际上更快取决于许多事情，例如：数组包含多少数据，数组1与数组2中的数据比例是多少（一个数组包含的数据是否比另一个数组多）？等等。

注意：您可能应该从简单的解决方案开始，并且只有在遇到性能问题时才进行优化。但是，使用大型数据集进行测量，以查看您的解决方案是否适用于您的用户可能拥有的任何数据。

将一个排序数组中的项目插入另一个排序数组

如果您想通过在正确的位置插入对象来合并两个数组，则应用普通算法。您应该将较小的数组插入到较大的数组中，并尝试在可能的情况下插入整个排序序列，而不是一个一个地插入每个项目。

为了获得最佳性能，您应该尝试使用insertObjects:atIndexes:而不是一个一个地插入对象来进行批量插入。

如果您为选项指定，您可以使用它indexOfObject:inSortedRange:options:usingComparator:来查找每个项目应插入到另一个数组中的索引。NSBinarySearchingInsertionIndex此外，您使用的比较器必须与对数组排序的比较器相同，否则结果为“未定义”。

考虑到这一点，你会做这样的事情

Create mutable index
For every ITEM in SMALLER ARRAY
    Find the index where to insert ITEM in LONGER ARRAY
    Add (the insertion location + the location in the short array) as the index in the mutable set.
Next item.

Batch insert all items.

的文档insertObjects:atIndexes:告诉您“已进行较早插入后在索引中指定的相应位置”。在您使用两个排序数组的情况下，这意味着所有具有较低索引的项目都已添加，因此您应该将短数组中对象的索引添加到从indexOfObject:inSortedRange:options:usingComparator:.

您可以做的另一个（可能非常过早的优化）是减少循环中每个项目的 sortedRange，这样您就不必搜索您知道要插入的项目大于的数组部分。

可能还可以进行许多其他优化。你还是应该先测量！希望这会让你开始。

于 2012-06-11T13:46:19.103 回答
2 
NSArray *newArray=[firstArray arrayByAddingObjectsFromArray:secondArray];
newArray = [newArray sortedArrayUsingSelector:@selector(localizedCaseInsensitiveCompare:)];
于 2012-06-11T13:46:35.537 回答
2

我会先简单地将第一个数组的所有对象添加到第二个数组中，然后再使用第二个数组。时间需要多长时间。如果可以接受，就停在那里。

如果没有，您可以尝试二进制搜索以在第二个数组中为第一个数组中的每个项目找到插入点。由于两个数组都已排序，因此您可以通过使用最后一个插入点作为每次循环的下限来优化搜索。像这样的东西：

NSInteger insertionPoint = -1;
for (id object in array1)
{
    insertionPoint = [self binarySearch: array2 for: object lowerBound: insertionPoint + 1];
    [array2 insertObject: object atIndex: insertionPoint];
}
于 2012-06-11T15:13:04.893 回答
1

Cocoa 类NSSortDescriptor和sortedArrayUsingDescriptors:fromNSArray应该做你所追求的。

由于您使用的是可变数组，因此您可能希望使用sortUsingDescriptors:which 对可变数组进行排序而不创建新数组。

于 2012-06-11T13:46:11.167 回答
0

查看此处的文档，看看是否有任何 NSArray 排序方法适合您。http://developer.apple.com/library/mac/#documentation/Cocoa/Reference/Foundation/Classes/NSArray_Class/NSArray.html。您可以向下滚动到方法，并且有 7 个用于排序的内置方法。您可能只需组合这两个数组并运行 sortedArrayUsingComparator: 或其他方法之一。

于 2012-06-11T13:48:14.610 回答