从软工毕业学长那里淘来一本《啊哈！算法》
然后跟着这本书学习学习，记录一下
桶排序
在生活中会遇到一些排序问题，比如站队列的时候要按身高排序、考试的名次要按分数排序、网上购物有时会按价格排序……
对于一组很简单的数字，桶排序无疑是最快最简单的
“桶” 的理解：一个一维数组，大小为输入数字的最大值 + 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）
后面再学习其他的罢
