全文目录
☘前言☘
🎁主要知识点梳理
📝1.排序
🥗1.1 排序简介
🥙1.2 qsort简介
🥪1.3 qsort调用
🌮1.4 比较函数
🌯1.5 更多比较函数
🍗课后习题
912. 排序数组
169. 多数元素
217. 存在重复元素
164. 最大间距
905. 按奇偶排序数组
539. 最小时间差
976. 三角形的最大周长
881. 救生艇
📑写在最后
🎁主要知识点梳理
📝1.排序
🥗1.1 排序简介
排序可能是我们接触的第一个算法，从最简单的冒泡排序、选择排序、插入排序到归并排序、希尔排序、快排等，还有一些有趣的基数排序和计数排序、桶排序等。
但是今天我们用用造好的轮子——C语言的排序API
🥙1.2 qsort简介
void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void*, const *void));
🥪1.3 qsort调用
int a[5] = {5, 4, 3, 2, 1}; qsort(a, 5, sizeof(int), cmp);
执行之后就会变为{1, 2, 3, 4, 5}，其中的cmp函数是需要我们自己去实现的。
🌮1.4 比较函数
1.函数原型
int compar(cont void *p1, const void *p2);
如果compar返回值大于0，则p1所指向元素会被排在p2后面。
如果compar返回值小于0，则p1所指向元素会被排在p2前面。
如果compar返回值等于0，则p1所指向元素与p2指向元素舒徐不确定。
2.函数定义
如果我们需要一个递增排序可以这么写：
int cmp(const void*p1, const void *p2) { int v1 = *(int *)p1; int v2 = *(int *)p2; if(v1 < v2) { return -1; }else if(v1 > v2) { return 1; } return 0; }
其中的传入参数是和定义保持一致，如果不一致会有警告信息，其实也没啥事0.0
然后v1和v2是取到要排序的元素，然后进行比较。
3.简化写法
如果确保数组相减不超过32位，也可以这么写：
int cmp(const void *p1, const void *p2) { return (*(int *)p1) - (*(int *)p2); }
🌯1.5 更多比较函数
我们可以实现递减的函数：
int cmp(const void *p1, const void *p2) { return (*(int *)p2) - (*(int *)p1); }
如果偶数在前 奇数在后
int Qua(int x) { return x % 2; } int cmp(const void *p1, const void *p2) { return Qua(*(int *)p1) - Qua(*(int *)p2); }
