数组排序

http://blog.ablepear.com/2011/11/objective-c-tuesdays-sorting-arrays.html

使用qsort()为C数组排序

C标准库包含一个内置的为数组排序的方法:qsort(),这是快速排序算法的一个实现。其排序之后的结果仍然放在原数组中

qsort() 的函数声明是这样:

qsort(void *array, size_t itemCount, size_t itemSize,
     int (*comparator)(void const *, void const *));

如果你没有在C中使用过函数指针，qsort()的函数声明看上去会有点让人迷惑。这是因为声明一个C函数指针类型有点唬人。我会用typedef让它看上去容易理解一些：

// alternate declaration of qsort using a typedef:
typedef int (*Comparator)(void const *, void const *);

qsort(void *array, size_t itemCount, size_t itemSize,
     Comparator comparator);

函数指针和函数的声明在C中是大体相同的，唯一的区别是函数指针在函数名前有一个*，像其他变量类型的指针一样。但有一个问题。在一个函数指针的声明里，*会引起歧义;默认情况下,C会认为*是函数返回省的一部分.因些当你声明一个函数指针的时候,需要为*和函数名加括号.这样便于编译器识别.

// 声明一个函数，返回int类型的指针
int *returnAPointerToSomeInt(void);
// 与下面这个声明相同:
// (int *)returnAPointerToSomeInt(void);

// 声明一个函数指针，这个函数返回类型是int
int (*returnSomeInt)(void);

既然我们已经说清楚了函数指针，让我们再来看看qsort()的函数声明

typedef int (*Comparator)(void const *, void const *);

qsort(void *array, size_t itemCount, size_t itemSize,
     Comparator comparator);

qsort()的前三个参数指定了要排序的数组，数组中元素的数量和单元元素的大小(字节数)
注意数组的类型是 void *,这就允许我们可以为任意类型的数组排序.

最后一个参数是比较函数.

typedef int (*Comparator)(void const *item1, void const *item2);

比较函数使用两个指向数组中元素的指针，如果item1在item2前，返回一个负值，如果item1在item2后，返回一个正值，如果两个元素有相同的排序值，返回0.这种风格的比较函数被用在许多语言的排序中. 理解比较函数可以看下面的图:


  item1 <=====<< item2
<-+------+-----+------+------+->
-2     -1     0      1      2

          item2 >>=====> item1
<-+------+-----+------+------+->
-2     -1     0      1      2

C标准库没有太多的比较函数，但比较函数很容易编写。这里是个比较int类型数据的例子:

int compareInts(void const *item1, void const *item2) {
 int const *int1 = item1;
 int const *int2 = item2;
 return *int1 - *int2;
}

现在我们可以使用compareInts()来排序一个int型的数组了：

int array[6] = { 42, 17, 57, 19, 11, 5 };

qsort(array, 6, sizeof(int), compareInts);
// array now contains 5, 11, 17, 19, 42, 57

qsort()非常灵活.对复杂类型的数组进行排序和对int类型的数组一样简单.为一个C string数组按词典排序，可以使用标准库中的strcmp()作为比较函数.

char const *array[3] = { "red", "green", "blue" };

qsort(array, 3, sizeof(char const *), strcmp);
// array now contains "blue", "green", "red"

为一个CGPoints的数组排序，先写一个比较函数：

int compareCGPoints(void const *item1, void const *item2) {
 struct CGPoint const *point1 = item1;
 struct CGPoint const *point2 = item2;

 if (point1->x < point2->x) {
   return -1;
 } else if (point1->x > point2->x) {
   return 1;
 }

 if (point1->y < point2->y) {
   return -1;
 } else if (point1->y > point2->y) {
   return 1;
 }

 return 0;
}

注意我们先比较点的X坐标，只在X坐标相等的情况下才比较Y坐标.这是比较struct中多个字段的通用方式。这是一个CGPoint比较的例子：

struct CGPoint pointArray[4] = {
 { 4.0f, 3.0f },
 { 2.0f, 1.0f },
 { 4.0f, 1.0f },
 { 2.0f, 3.0f }
};
qsort(pointArray, 4, sizeof(struct CGPoint), compareCGPoints);
// pointArray now contains:
//  { 2.0f, 1.0f }
//  { 2.0f, 3.0f }
//  { 4.0f, 1.0f }
//  { 4.0f, 3.0f }

其他C排序函数
对于大多数的普通排序工作,qsort()是个不错的选择，并且是C标准库是的内置的唯一选择。OS X和iOS也包含其他一些值得一提的排序函数:heapsort()和mergesort(),它们和qsort使用同样的参数.heapsort() 比qsort() 慢,但是排序过程中使用有限的内存, qsort() 使用递归并且可能导致堆栈溢出. 当数组已经大分部已经有序的情况下mergesort()比qsort()快很多,但是在数组很随机的情况下会慢很多.

NSArray排序

Objective-C 提供许多 NSArray排序的方法.因为NSArray 对象是不可修改的,所以用于排序 NSArray 的方法都返回一个新的排序好的 NSArray 对象，原始的NSArray不变. 最基本的排序方法是-sortedArrayUsingFunction:context:, 它和使用qsort()排序 C 相似. 函数声明是这样:

- (NSArray *)sortedArrayUsingFunction:(NSInteger (*)(id, id, void *))comparator 
                              context:(void *)context

第一个参数是比较函数的指针，
像我们为 qsort()做的那样, 我将要使用typedef重写函数指针方法声明，以便于阅读:

typedef NSInteger (*Comparator)(id item1, id item2, void *context);

- (NSArray *)sortedArrayUsingFunction:(Comparator)comparator 
                              context:(void *)context

NSArray排序用的比较函数和qsort的比较函数稍有不同.它的返回值是NSInteger类型的,其实NSInteger只是int的一个typedef.它使用两个id类型的元素，而不是void const *,因为 NSArrays 只能容纳 object 类型.并且最后，还有一个额外的 context 参数, 一个 void 指针，这个指针允许你传递额外的信息给比较函数.

让我们写一个按NSString长度排序的比较函数.

static NSInteger compareStringsByLength(id item1, id item2, void *context) {
  return [item1 length] - [item2 length];
}

因为我们可以传递任务消息给一个id类型的变量，所以我们甚至不需要类型转换或中间变量.

下面看看我们怎么使用它：

NSArray *array = [NSArray arrayWithObjects:@"Florida", 
                    @"Texas", @"Mississippi", @"Delaware", nil];

NSArray *sortedArray = [array sortedArrayUsingFunction:compareStringsByLength 
                                               context:NULL];
// sortedArray contains:
// @"Texas"
// @"Florida"
// @"Delaware"
// @"Mississippi"

现在让我们使用context参数来方便地在普通和逆序排序之间切换.我们能传递参数给任务类型的数据，所以我们使用一个BOOL类型的指针,YES代表逆序,NO代表普通排序.

NSInteger compareStringsByLength(id item1, id item2, void *context) {
  BOOL *reversed = context;
  NSInteger order = [item1 length] - [item2 length];
  if (*reversed) {
    return -order;
  } else {
    return order;
  }
}

现在我们需要传递值给context参数当我们调用-sortedArrayUsingFunction:context:的时候：

NSArray *array = [NSArray arrayWithObjects:@"Florida", 
                    @"Texas", @"Mississippi", @"Delaware", nil];

BOOL reversed = YES;
NSArray *sortedArray = [array sortedArrayUsingFunction:compareStringsByLength 
                                               context:&reversed];
// sortedArray contains:
// @"Mississippi"
// @"Delaware"
// @"Florida"
// @"Texas"

注意我们用&操作符来传递变量reversed的地址作为context.

如果你的目标系统是iOS3.2, OS X 10.6以上,你可以用block版,-sortedArrayUsingComparator:. 我们可以这样重写我们的例子：

NSArray *array = [NSArray arrayWithObjects:@"Florida", 
                    @"Texas", @"Mississippi", @"Delaware", nil];

BOOL reversed = YES;
NSArray *sortedArray = [array sortedArrayUsingComparator:^(id item1, id item2) {
  NSInteger order = [item1 length] - [item2 length];
  if (reversed) {
    return -order;
  } else {
    return order;
  }
}];
// sortedArray contains:
// @"Mississippi"
// @"Delaware"
// @"Florida"
// @"Texas"

因为所有在NSArray中的元素必需是对象，经常的情况是这些元素自身带有比较方法.如果是这样的话，-sortedArrayUsingSelector: 方法非常好。NSString类型的NSArray非常常见.

NSArray *tagNames = [NSArray arrayWithObjects:@"H1", 
                    @"body", @"A", @"Head", nil];

NSArray *sortedTagNames = [tagNames sortedArrayUsingSelector:@selector(caseInsensitiveCompare:)];
// sortedTagNames contains:
// @"A"
// @"body"
// @"H1"
// @"Head"