上一篇: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,其他几个函数则一定会排序成功。
描述:
示例代码:
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,否则返回其他。
功能:
示例代码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标准库中常用数据结构和算法之二叉排序树