iOS标准库中常用数据结构和算法之排序

🎢排序

排序是指将乱序数组变为有序排列的处理。iOS提供了快速排序、堆排序、归并排序、并行排序、基数排序一共5种排序函数。具体每种排序的概念介绍请大家参考相关的文档这里就不再赘述了。下面的表格将会从时间复杂度、稳定性、是否需要分配额外内存、是否对有序数组进行优化、应用范围、平台支持6个维度来考察各种排序函数：

排序算法	时间复杂度	是否稳定	是否需要分配额外内存	是否对有序数组进行优化	应用范围	平台支持
快速排序	N*logN	否	递归栈内存	无	任意数组	POSIX
堆排序	N*logN	否	无	有	任意数组	BSD UNIX/iOS
归并排序	N*logN	是	有	有	任意数组	BSD UNIX/iOS
并行排序	N*logN	否	有	无	任意数组	iOS
稳定基数排序	N*D	是	有	无	字节串	BSD UNIX/iOS
不稳定基数排序	N*D	否	无	无	字节串	BSD UNIX/iOS

一、快速、堆、归并、并行排序

功能：这四类排序函数的参数都是一致的，所以列在一起进行介绍。
头文件：#include <stdlib.h>
平台：qsort被POSIX支持、psort为iOS独有、其他的都被BSD Unix支持
函数签名：

//快速排序
void qsort(void *base, size_t nel, size_t width, int (*compar)(const void *, const void *));
//快速排序block版本
void qsort_b(void *base, size_t nel, size_t width, int (^compar)(const void *, const void *));
//快速排序附加参数版本
void qsort_r(void *base, size_t nel, size_t width, void *thunk, int (*compar)(void *, const void *, const void *));

//堆排序
int heapsort(void *base, size_t nel, size_t width, int (*compar)(const void *, const void *));
//堆排序block版本
int heapsort_b(void *base, size_t nel, size_t width, int (^compar)(const void *, const void *));

//归并排序
int mergesort(void *base, size_t nel, size_t width, int (*compar)(const void *, const void *));
//归并排序block版本
int mergesort_b(void *base, size_t nel, size_t width, int (^compar)(const void *, const void *));

//并行排序
void psort(void *base, size_t nel, size_t width, int (*compar)(const void *, const void *));
//并行排序block版本
void psort_b(void *base, size_t nel, size_t width, int (^compar)(const void *, const void *));
//并行排序附加参数版本
void psort_r(void *base, size_t nel, size_t width, void *thunk, int (*compar)(void *, const void *, const void *));

参数：
base:[in/out] 参与排序的数组的首地址。
nel:[in] 数组的元素的个数。
width:[in] 数组中每个元素的尺寸。
compar: [in] 函数比较器，排序时会通过对数组中的两个元素调用函数比较器来判断排序的顺序。函数比较器的格式如下：

/*
@thunk: 函数比较器的附加参数，其值就是上述的带附加参数版本的排序函数的thunk参数。
@element1, element2: 元素在数组中的地址，这里需要注意的是这个参数不是元素本身，而是元素所在的数组中的偏移地址。
@return: 如果比较结果相等则返回0, 如果element1在element2前返回小于0，如果element1在elemen2后面则返回大于0
*/
 int compar(const void *element1, const void *element2);
 //带附加参数版本
 int compar(void *thunk, const void *element1, const void *element2);

return:[out] 对于堆排序和归并排序来说有可能会排序失败，如果排序成功会返回0否则返回非0，其他几个函数则一定会排序成功。

描述：

qsort函数是用于快速排序的函数，采用的是C.A.R. Hoare 所实现的快速排序算法。快速排序是一种不稳定排序，排序速度最快，平均时间复杂度为O(N*logN)，因为其并未对有序数组进行优化处理，因此最差的时间可能是O(N^2)。快速排序内部采用递归的机制进行排序，因此没有额外的内存分配，当然如果数组元素数量众多则过度的递归可能会导致栈溢出，因此其内部实现如果超过了约定的递归次数后就会转化为堆排序。
heapsort函数是用于堆排序的函数，采用的是J.W.J. William所实现的堆排序算法。堆排序是一种不稳定排序，其时间复杂度比较稳定为O(N*logN)。堆排序对有序数组进行优化处理。堆排序进行排序时几乎没有附加内存的分配和消耗处理。
mergesort函数是用于归并排序的函数，归并排序是一种稳定的排序，平均时间复杂度为O(N*logN), 因为其对有序数组进行了优化处理，因此最好的时间可能达到O(N)。归并排序的缺点是有可能会在排序实现内部分配大量的额外内存(排序数组的尺寸)，所以不适合用在数组元素过多的排序中。
psort函数是用于并行排序的函数，这函数是iOS系统独有的函数。并行排序也是一种不稳定的排序。当数组的元素数量小于2000或者CPU是单核时并行排序内部使用快速排序qsort来实现，而当数量大于2000并且是多核CPU时系统内部会开辟多线程来执行并行的排序处理。因此当数量众多而且又希望能并行处理时可以用这个函数来进行排序，当然缺点就是排序时有线程创建和调度的开销。
上述的排序函数有_r结尾的表明是带有附加参数的排序函数，这样在比较器中就可以使用这个附加参数，从而实现一些扩展的能力，这个就和带_b结尾的用block进行比较的元素比较能力是一样。

示例代码:

int compar(const void *element1, const  void *element2)
{
   //注意这里的element1,element2是元素在数组中的指针而非元素本身
    const char *p1 = *(const char **)element1;
    const char *p2 = *(const char **)element2;
    return strcmp(p1, p2);
}

void main()
{
     char *arr[6] = {"Bob","Max","Alice","Jone","Lucy","Lili"};
    
      qsort(arr, sizeof(arr)/sizeof(char*), sizeof(char*), compar); 
      heapsort(arr, sizeof(arr)/sizeof(char*), sizeof(char*), compar); 
      mergesort(arr, sizeof(arr)/sizeof(char*), sizeof(char*), compar); 
      psort(arr, sizeof(arr)/sizeof(char*), sizeof(char*), compar); 
}

基数排序

功能：基数排序是利用了排序元素取值的一些限制来进行排序的排序方式。因此基数排序并不能适用于任何的数据结构。就以系统提供的函数来说，目前只支持基于字节串数组(字节串包括字符串)的排序。系统为基数排序分别提供了稳定和非稳定两种版本的排序函数。要想更加详细的了解基数排序请参考相关的文档。

头文件：#include <stdlib.h>, #include <limits.h>
平台：BSD Unix
函数签名：

//基数排序非稳定版
int radixsort(const unsigned char **base, int nmemb, const unsigned char *table,unsigned endbyte);
//基数排序稳定版,稳定版排序会有double的附加内存分配
int sradixsort(const unsigned char **base, int nmemb, const unsigned char *table,unsigned endbyte);

参数：
base: [in/out]: 字节串数组指针。
nmemb:[in] 字节串数组元素个数。
table:[in] 可以传NULL或者一个长度为256的数组。因为一个字节符号的编码取值范围是0-255，所以这个表中的每个元素的值就表明每个字节符号的比重值，其取值也是0-255。这个表用来决定基数字节串数组的排序是升序还是降序，如果表中的值分别是从0到255那么字节串就按升序排列，如果表中的值分别是从255到0则表示按降序排列。同时这个表还可以用来决定是否对字符的大小写敏感，举例来说对于字符A-Z以及a-z的字节编码值不一样，因此如果table中对应位置的比重值不一样那么就表示是大小写敏感，而如果将表中对应位置的比重值设置为一样，那么就可以实现大小写不敏感的排序了。具体的对table的使用将会在下面的例子中有详细说明。如果我们不想自定义排序规则那么将这个参数传递NULL即可表明按升序进行排序。
endbyte:[in] 每个字节串的结尾字节值，因为基数排序不局限于字符串，也可以用在字节串上，所以需要有一个标志来标识每个字节或者字符串是以什么字节结尾的。默认情况下的字符串一般都是以'\0'结尾，所以这个参数对于常规字符串来说传0即可。
return:[out] 返回排序成功与否，成功返回0，否则返回其他。

功能：

基数排序只能对字节串数组进行排序，而不能对任意的数据结构进行排序处理，因此其排序具有一定的局限性。基数排序的时间复杂度为O(N*D)，这里的D是指待排序字节串中最长的字节串的长度，因此基数排序几乎接近于线性时间的长度了。
基数排序中的table表决定着基数排序的排序顺序和结果。这个表所表达的每个字节编码的比重值。因为字节的编码是从0到255，而默认的每个字节的比重值和编码值相等，这样就表明着字节串将按照编码的大小进行升序排列。
基数排序分为稳定版本和不稳定版本，二者的区别就是当值相同时，是否会位置保持而不被交换。稳定版基数排序的一个缺点就是会产生双倍大小的额外内存分配。

示例代码1：

void main()
{
   char *arr[6] = {"Bob","Max","Alice","ada","lucy","Lili"};
    
    //默认升序排列
    radixsort(arr, sizeof(arr)/sizeof(char*), NULL, '\0');
    
    //降序排列，这里需要构建table表，其比重顺序变为由大到小。
    unsigned char table1[UCHAR_MAX + 1] = {0};
    for (int i = 0; i < UCHAR_MAX + 1; i++)
        table1[i] = UCHAR_MAX - i;    //每个字节编码位置的比重值由大到小
    radixsort(arr, sizeof(arr)/sizeof(char*), table1, '\0');
    
    
    //大小写不敏感升序排序，这里需要构建table表，将大写字母和小写字母的比重值设置为一致。因为上面的排序内容只有字母符号所以只需要修改字母符号位置的比重值即可。
    unsigned char table2[UCHAR_MAX + 1] = {0};
    for (int i = 'A';i <= 'Z'; i++)
    {
        table2[i] = i;
        table2[i+32] = i;  //小写部分的比重值也设置和大写部分的比重值一致。
    }
    radixsort(arr, sizeof(arr)/sizeof(char*), table2, '\0');
}

示例代码2：
虽然基数排序正常情况下只能用于字节串数组进行排序，如果字节串是某个结构体的成员时，我们希望整个结构体也跟着排序。这时候就需要进行结构体的特殊设计，我们需要将结构体的第一个数据成员设置为字节串数组即可实现将结构体来应用基数排序。具体的代码如下：

//对结构体的排序。要求字符串作为结构体的第一个成员，而且字符串成员必须是数组，而不能是字符串指针。
    typedef struct student
    {
        char name[16];    //结构体中字符串必须以数组的形式被定义并且作为第一个数据成员。
        int age;
    }student_t;
    
    student_t *a1 = malloc(sizeof(student_t));
    strcpy(a1->name, "Bob");
    a1->age = 10;
    
    student_t *a2 = malloc(sizeof(student_t));
    strcpy(a2->name, "Jone");
    a2->age = 15;
    
    student_t *a3 = malloc(sizeof(student_t));
    strcpy(a3->name, "Alice");
    a3->age = 12;
    
    student_t *a4 = malloc(sizeof(student_t));
    strcpy(a4->name, "Tom");
    a4->age = 12;
    
    student_t *a5 = malloc(sizeof(student_t));
    strcpy(a5->name, "Lucy");
    a5->age = 8;
    
    student_t *a6 = malloc(sizeof(student_t));
    strcpy(a6->name, "Lily");
    a6->age = 18;
    
    student_t *arr[6] = {a1,a2,a3,a4,a5,a6};
    radixsort(arr, 6, NULL, '\0');

下一篇：iOS标准库中常用数据结构和算法之二叉排序树

欢迎大家访问欧阳大哥2013的github地址和简书地址