NSArray使用什么排序函数? [英] What sort function is used in NSArray?

问题描述

这确实是一个由三部分组成的问题，但我本人已经回答了第一个问题:

This is really a three-part question, but I've answered the first question myself:

我正在使用iPhone，屏幕上有很多对象(最多200个).每个对象都需要查看其是否与其他对象重叠，并采取相应的措施.我最初的天真实现是让每个对象遍历每个对象的列表以检查其边界框(使用CGRectInsersectsRect).

I'm working on the iPhone, with many objects (up to 200) on the screen. Each object needs to look if it's overlapping other objects, and act accordingly. My original naive implementation was for each object to run through the list of each other object to check their bounding boxes (using CGRectInsersectsRect).

所以我的问题(和答案)是什么更好的方法?我的新实现是在每个对象的y位置使用插入排序(因为数据已经大部分进行排序)对每个帧进行排序，然后仅在一次搜索的任一侧检查最近的对象，以查看是否垂直在范围内，然后水平检查.

So my question (and answer) is what's a better method? My new implementation is to sort the array every frame using an insertion sort (since the data will be mostly sorted already) on the y-position of each object, then check only the nearest object on either side of the one searching, to see if it's in range vertically, then check horizontally.

第一个问题:插入排序是我要用于趋向于随机移动但仅在很小范围内移动的对象数组的一种方法，因此它们大多基于最后一帧而保持顺序吗?另外:调用时，NSArray使用哪种排序算法

First question: Is insertion sort the method I want to use for an array of objects that tend to move around randomly but only to a small extent so they mostly stay in order based on the last frame? Also: what sort algorithm does the NSArray use when I call

- sortedArrayUsingSelector:

我会假设它使用快速排序，因为在一般情况下它是最有用的.有人知道我错了吗?有人知道我是否可以更改排序方法，或者是否必须编写自己的排序函数?

I would sort of assume that it uses a quick sort, since it's the most useful in the general case. Does anybody know if I'm wrong? Does anybody know if I can change the sort method or if I will have to write my own sorting function?

第二个问题:是否存在使用二进制搜索从排序数组中检索项目的功能，而不是我假定的天真的方法

Second question: is there a function for retrieving items from a sorted array using a binary search, rather than the naive approach that I assume is used by

- indexOfObject:

还是我必须写我自己的书?

or would I have to write my own?

推荐答案

NSArray内部使用许多不同的数据结构，具体取决于数组中有多少个对象.有关更多信息，请参见 Peter Ammon博客条目.但这基本上意味着您无法期望某种特定类型的事件发生.有时值得使用C数组编写自己的数组实现，以便您可以自己控制排序.

NSArray uses many different data structures internally depending on how many objects are in the array. See a Peter Ammon blog entry for more information. But basically this means you can't expect a certain kind of sort to happen. Sometimes it is worth it to write your own array implementation using C arrays so you can control the sorts yourself.

肯定有更快的方法来实现碰撞检测.查看诸如KD树之类的边界体积层次结构.

There are definitely much faster ways to implement collision detection. Look into Bounding Volume Hierarchies like KD Trees or similar.

据我所知，indexOfObject:是唯一的方法，但它可能不像您想象的那样愚蠢. NSDictionary的所有内容都是可哈希的，因此他们可以在NSArray中使用其中一些智能功能.

As far as I know indexOfObject: is the only way, but it's potentially not as dumb as you think. Everything is hashable for NSDictionary so they can use some of those smarts in NSArray.

这篇关于NSArray使用什么排序函数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！