全文目录

 ☘前言☘

🎁主要知识点梳理

         📝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);
}