第一节 桶排序 （最快最简单的排序）
1、概括
就实现申请大小为的数组为例，int a[11]。首先将所有变量初始化为0，表示还没有出现过任何数字。
下面开始处理得到的数字：
若存入的第一个数字是5，就将相对应的a[5]的值在原来的基础上增加1.即将a[5]的值从0改为1，表示5出现过一次。
若第二个数字是3，将相对应的a[3]的值在原来的基础上增加1，即a[3] = 1。
注意！如果下一个数字也是5，将a[5]的值在原来的基础上+1，即a[5]++;
以此类推，处理第四个数字 “2” 和第五个数字 “8” ，最终得到下面的图.
或者可以用插旗子更加直观一些
2、代码实现
// 排序1000以内的数字，降序输出结果
#include <stdio.h>
int main()
{
int book[1001], i, j, t, n;
for (i = 0; i <= 1000; i++)
{
book[i] = 0; // 将所有的元素初始化为0
}
printf("请输入元素个数：");
scanf("%d", &n); // 输入一个数字n，表示接下来有n个数
if (n < 0 || n > 1000)
{
printf("输入的 'n' 无效。应该在 0 到 1000 之间。\n");
return 1; // 以错误代码退出程序。
}
printf("请输入 %d 个元素:\n", n);
for (i = 1; i <= n; i++) // 循环读入n个数字，并且进行桶排序
{
scanf("%d", &t); // 将每个数读到变量t中
if (t < 0 || t > 1000) // 错误检测
{
printf("输入的 't' 无效。应该在 0 到 1000 之间。\n");
return 1; // 以错误代码退出程序。
}
book[t]++; // 进行计数，对编号为t的桶放一个“旗子”
}
// 降序排序
for (i = 1000; i >= 0; i--) // 依次判断编号1000~1的桶
{
for (j = 1; j <= book[i]; j++) // 出现了几次小旗子就将桶的编号打印几次
{
printf("%d ", i);
}
}
getchar();
getchar(); // 暂停程序
return 0;
}
如果要实现升序排序，只需要将
改为此即可
3、总结：
1、第一个for循环，循环了m次（桶的个数）。第二个for循环，循环了n次。第三个for循环，循环了m+n次。共循环了m+n+m+n次，即时间复杂度为O(2*(m+n)) -> O(M+N)。
2、浪费空间。必须根据数组的大小进行排序，如果我要排序10000和1，那就需要定义a[10001]，数组太大，需要遍历到10000。上文只是简单介绍桶排序，真正的桶排序很复杂，解决了这个问题。
3、局限性太大。现有3个人的名字和分数，张三：86分，李四：98，王五：68，请按照分数进行升序排序，打印结果 “王五，张三，李四”，但是桶排序只能排序出成绩，无法输出名字，我们无法知道排序后的分数原本对应的哪一个人。这该怎么办呢？请看下节，冒泡排序
第二节 冒泡排序
1、概括
冒泡排序的基本思想是：每次比较两个相邻的元素，如果它们的顺序错误就把它们交换过来。
冒泡排序是我大一接触的第一个算法，比较简单，直接给出例子吧。
2、代码展示：
#include <stdio.h>
int main()
{
int a[100], i, j, n, t;
scanf("%d", &n); // 输入需要排序的数字个数
for (i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
}
// 核心部分
for (j = 1; j <= n - 1; j++) // 相邻对比
{
for (i = 1; i < n; i++)
{
if (a[i] < a[i + 1]) // 比较大小并转换
{
t = a[i];
a[i] = a[i + 1];
a[i + 1] = t;
}
}
}
for (i = 1; i <= n; i++) // 输出结果
{
printf("%d ", a[i]);
}
getchar();
return 0;
}
运行结果如下：
将上面的代码稍加修改，就可以解决第一节遗留的问题了
#include <stdio.h>
struct student
{
char name[21];
int score;
}; // 创建结构体存储姓名和分数
int main()
{
struct student a[100], t;
int i, j, n;
scanf("%d", &n); // 输入需要排序的数字个数
for (i = 1; i <= n; i++)
{
scanf("%s %d", a[i].name,&a[i].score);
}
// 核心部分
for (j = 1; j <= n - 1; j++) // 相邻对比
{
for (i = 1; i < n; i++)
{
if (a[i].score < a[i + 1].score) // 比较大小并转换
{
t = a[i];
a[i] = a[i + 1];
a[i + 1] = t;
}
}
}
for (i = 1; i <= n; i++) // 输出结果
{
printf("%s\n ", a[i].name);
}
getchar();
return 0;
}
运行结果如下
3、总结：
1、冒泡排序的核心是双重循环嵌套。实践复杂度是O(N^2)。时间复杂度太高，不值得推荐。
第三节 快速排序（最常用的排序）
1、概括
快速排序是跳跃式的排序，通过设置基准点，将大于基准点的放在右侧，小于的放在左侧。
下图直观化表示：
2、代码展示
#include <stdio.h>
#define MAX_SIZE 101 // 定义数组最大大小
int arr[MAX_SIZE], num; // 定义全局数组和变量
void quicksort(int left, int right) {
if (left > right) {
return; // 处理边界条件，确保不会越界
}
int i = left, j = right, temp, pivot = arr[left]; // 选择第一个元素作为基准数
while (i != j) {
while (arr[j] >= pivot && i < j) j--; // 从右向左找比基准数小的元素
while (arr[i] <= pivot && i < j) i++; // 从左向右找比基准数大的元素
if (i < j) {
temp = arr[i]; // 交换元素位置
arr[i] = arr[j];
arr[j] = temp;
}
}
arr[left] = arr[i]; // 将基准数归位
arr[i] = pivot;
quicksort(left, i - 1); // 递归调用，对左半部分排序
quicksort(i + 1, right); // 递归调用，对右半部分排序
}
int main() {
printf("请输入要排序的元素个数：");
scanf("%d", &num); // 输入元素个数
if (num < 0 || num > MAX_SIZE) {
printf("输入的元素个数无效。请确保在 0 到 %d 之间。\n", MAX_SIZE);
return 1; // 以错误代码退出程序
}
printf("请输入 %d 个元素:\n", num);
for (int i = 1; i <= num; i++) {
scanf("%d", &arr[i]); // 输入元素
}
quicksort(1, num); // 调用快速排序函数
printf("快速排序的结果为：");
for (int i = 1; i <= num; i++) {
printf("%d ", arr[i]); // 输出排序结果
}
printf("\n");
return 0;
}
运行结果展示
3、总结
1、快速排序的时间复杂度是不确定的，最差的结果是O(N^2)，他的平均时间复杂度是O(NlogN)。
2、冒泡排序解决了桶排序浪费空间的问题，但是算法的执行效率牺牲了很多。而快速排序既不浪费空间，也可以快一点排序。