从软工毕业学长那里淘来一本《啊哈！算法》
然后跟着这本书学习学习，记录一下
桶排序
在生活中会遇到一些排序问题，比如站队列的时候要按身高排序、考试的名次要按分数排序、网上购物有时会按价格排序……
对于一组很简单的数字，桶排序无疑是最快最简单的
“桶”的理解：一个一维数组，大小为输入数字的最大值+1，数组的每一个下标都是一个标签，默认每一个数组元素的值都是0，当遍历到变量值等于下标值的时候呢，这个数组元素的值就自增，最后这个一维数组的值就有0或非0，只需要按下标大小取出元素值就能完成排序。
例如：输入5个数字，并从大到小输出
用C语言代码实现就是这样👇（编译器为VS 2022，一些关键字会有所不同
#include<stdio.h>
int main()
{
int a[21];
for (int i = 0; i < 21; i++)
a[i] = 0;//初始化数组为0
for (int i = 0; i < 5; i++)
{
int num;
scanf_s("%d", &num);
a[num]++;
}
for (int i = 20; i >= 0; i--)
{
if (a[i] != 0)
{
for (int j = 0; j < a[i]; j++)
{
printf("%d ", i);
}
}
}
return 0;
}排序是可以实现了，那么想想有什么弊端？
桶排序是基于数组的下标实现的
那么肯定会存在这些问题：
- 数字不能为负数或者小数
- 数字不能大于数组的最大值-1
- 数组也不能太大，不然会十分浪费空间
下面是一道有关桶排序的洛谷题：
给定一个字符串 s ，根据字符出现的 频率 对其进行 降序排序 。一个字符出现的 频率 是它出现在字符串中的次数。
示例：
输入: s = “tree”
输出: “eert”
解释: ‘e’出现两次，’r’和’t’都只出现一次。
因此’e’必须出现在’r’和’t’之前。此外，”eetr”也是一个有效的答案。
提示：
1 <= s.length <= 5 * 105s由大小写英文字母和数字组成
实现代码如下：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
char s[500001];
int a[130];
int cmp(char* p1, char* p2)
{
int n = a[*p1];
int m = a[*p2];
if (n == m)
{
return *p1 - *p2;//下标一样则按照字母顺序排列
}
return m-n;//下标不一样则按照频率排列
}
int main()
{
memset(a, 0, sizeof(a));
scanf_s("%s", s,500001);
int len = strlen(s);
for (int i = 0; i < len; i++)
{
a[s[i]]++;
}
qsort(s, len, sizeof(char), cmp);
printf("%s", s);
}这里涉及到了qsort快速排序函数，不过主体还是桶排序
冒泡排序
冒泡的基本思想是：每次比较两个相邻的元素，然后根据大小交换
下面是动态图演示：
这种排序的核心就是双重for循环进行遍历比较
网上随便找一段代码：
#include<stdio.h>
int main()
{
int n[10] = { 25,35,68,79,21,13,98,7,16,62 };//定义一个大小为10的数组
int i, j, temp;
for (i = 1; i <= 9; i++)//外层循环是比较的轮数，数组内有10个数，那么就应该比较10-1=9轮
{
for (j = 0; j <= 9 - i; j++)//内层循环比较的是当前一轮的比较次数，例如：第一轮比较9-1=8次，第二轮比较9-2=7次
{
if (n[j] > n[j + 1])//相邻两个数如果逆序，则交换位置
{
temp = n[j];
n[j] = n[j + 1];
n[j + 1] = temp;
}
}
}
for (i = 0; i < 10; i++)
printf("%d ", n[i]);
}
这是最基本的冒泡方法
可以在第一层for循环里设立判断，如果第二层for里没有进行交换则说明已经完成排序，就退出循环
不过当数组比较大的时候，使用冒泡排序并不是一个好的选择
快速排序
这是一种最常见的排序方式
基本思想：使用“分治”的策略，将序列分为两个子序列，并设立一个基准数（通常为第一个数字），比较基准数两侧的数据大小来排序（两侧并不是真的这个数字的两侧，而是序列的两侧）
比如说下面这种排列：
3 1 2 5 4 6 9 7 10 8
这时以数字6为基准数，左边都是小于6，右边则都是大于6，这是快速排序想要达到的效果
如何实现？
假如初始序列为这样：
6 1 2 7 9 3 4 5 10 8
分别从序列的两端开始探测，可以理解为两个指针向中间移动（）
以6为基准数，先从右往左找一个小于6的数字，再从左往右找一个大于6的数字，并将其交换（不是同时进行的
于是第一遍之后就找到 7 和 5 两个数字并交换
形成新的序列：
6 1 2 5 9 3 4 7 10 8
然后重复这样的操作
这里就省略一部分
最终会遇到这样的数列：
6 1 2 5 4 3 9 7 10 8
可以看到
从左往右找大于的时候左指针会指向7
从右往左找小于的时候右指针会指向3
而这种排序要求的是右指针要先于左指针移动
于是右指针停留在 3 ，左指针在移动的时候会在3与右指针相遇！
看看 3 和基准数 6 的位置关系呢？
将 3 和 6 交换一下便能发现此时序列为：
3 1 2 5 4 6 9 7 10 8
6的左边全是小于，而右边全是大于
至此第一轮探测便真正结束，6回到了正确的位置
不过 6 两侧的序列还是无序的，需要进行排序
基于这种思想，可以通过以下C代码实现快速排序
#include<stdio.h>
int a[101];
void quickSort(int left, int right)
{
int i, j, k, temp;
if (left > right)
return;
temp = a[left];//设立基准数，以左边的为基准数
i = left;
j = right;//可以看作两个指针,这里用下标来替代指针
while (i != j)
{
while (a[j] >= temp && i < j)
{
j--;//从右往左找，直到找到小于，或者跑到最左端，当然跑到最左端的话那么这个数字就是最大了，直接放到right去
}
while (a[i] <= temp && i < j)
{
i++;
}
if (i < j)//没有相遇的情况,就交换
{
k = a[i];
a[i] = a[j];
a[j] = k;
}
}
//最后归位基准数
a[left] = a[i];
a[i] = temp;
quickSort(left, i - 1);
quickSort(i + 1, right);//递归调用，分别处理两端序列
return;
}
int main()
{
int i, j, n;
scanf_s("%d", &n);
for (int c = 1; c <= n; c++)
{
scanf_s("%d", &a[c]);
}
quickSort(1, n);
for (int i = 1; i <= n; i++)
{
printf("%d ", a[i]);
}
return 0;
}
至于为什么非得从右边开始找，可以这样理解👇
给出一组序列：
6 1 2 7 9
先从左边找到 7
再从右边开始，到 7 的时候两个指针就相遇咯
按照上面说的，相遇那么就该归位
那么得到：
7 1 2 6 9
能发现结果不对啊！
问题就在于：如果我们先从左边开始找，那么找到的那个数字一定是大于基准数的，交换之后就违背了左小右大的原则
所以：我们必须从右边开始，也就是从基准数的对面开始。
快速排序还是要依靠数组，不过相较于冒泡，每次的交换都是跳跃式的
不过当序列处于完全逆序的情况下（最坏的情况），快排的时间复杂度和冒泡是一样的
简单的学习了一下三个基本的排序方式
排序方式不止这三种：
- 冒泡排序（Bubble Sort）
- 插入排序（Insertion Sort）
- 希尔排序（Shell Sort）
- 选择排序（Selection Sort）
- 快速排序（Quick Sort）
- 归并排序（Merge Sort）
- 堆排序（Heap Sort）
- 计数排序（Counting Sort）
- 桶排序（Bucket Sort）
- 基数排序（Radix Sort）
后面再学习其他的罢
