博客为参考《啊哈！算法》一书，自己所做的读书笔记。
本文为原创文章，未经本人允许，禁止转载。转载请注明出处。
1.最快最简单的排序-桶排序
👉相关博文：【算法基础】【排序】桶排序。
假设有5个学生，分数分别为5分、3分、5分、2分和8分。现在希望编写一段程序让计算机随机读入5个数然后将这5个数从小到大输出。
首先，我们申请一个大小为11的数组int a[11]：
数组下标表示对应的分数。我们将每个分数对应的人数存入数组中：
接下来，我们只需要将出现过的分数打印出来就可以了，出现几次就打印几次，具体如下：
a[0]为0，表示“0”没有出现过，不打印。a[1]为0，表示“1”没有出现过，不打印。a[2]为1，表示“2”出现过1次，打印2。a[3]为1，表示“3”出现过1次，打印3。a[4]为0，表示“4”没有出现过，不打印。a[5]为2，表示“5”出现过2次，打印5 5。a[6]为0，表示“6”没有出现过，不打印。a[7]为0，表示“7”没有出现过，不打印。a[8]为1，表示“8”出现过1次，打印8。a[9]为0，表示“9”没有出现过，不打印。a[10]为0，表示“10”没有出现过，不打印。
最终屏幕输出“2 3 5 5 8”，完整的代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<stdio.h>
int main()
{
int a[11],i,j,t;
for(i=0;i<=10;i++)
a[i]=0; //初始化为0
for(i=1;i<=5;i++)
{
scanf("%d",&t); //把每一个数读到变量t中
a[t]++; //进行计数
}
for(i=0;i<=10;i++) //依次判断a[0]~a[10]
for(j=1;j<=a[i];j++) //出现了几次就打印几次
printf("%d ",i);
getchar();getchar();
//这里的getchar();用来暂停程序，以便查看程序输出的内容
//也可以用system("pause");等来代替
return 0;
}
输入数据为：“5 3 5 2 8”。这个算法就好比有11个桶，编号从0～10。每出现一个数，就在对应编号的桶中放一个小旗子，最后只要数数每个桶中有几个小旗子就OK了：
桶排序是一个非常快的排序算法。但这个例子其实并不是真正的桶排序算法，真正的桶排序算法要比这个更加复杂。这个例子本质上还不能算是一个真正意义上的排序算法。为什么呢？例如遇到下面这个例子就没辙了。
现在分别有5个人的名字和分数：huhu 5分、haha 3分、xixi 5分、hengheng 2分和gaoshou 8分。请按照分数从高到低，输出他们的名字。即应该输出gaoshou、huhu、xixi、haha、hengheng。如果使用我们刚才简化版的桶排序算法仅仅是把分数进行了排序。最终输出的也仅仅是分数，但没有对人本身进行排序。
2.邻居好说话-冒泡排序
👉相关博文：【算法基础】【排序】冒泡排序。
简化版的桶排序不仅仅有上一节所遗留的问题，更要命的是：它非常浪费空间！例如需要排序数的范围是0～2100000000之间，那我们需要申请2100000001个变量，也就是说要写成int a[2100000001]。即便只给5个数进行排序，我们也仍然需要2100000001个“桶”，这真是太浪费空间了！还有，如果现在需要排序的不再是整数而是一些小数，那又该怎么办呢？因此，我们引入冒泡排序来解决这两个问题。
冒泡排序的原理介绍详见：【算法基础】【排序】冒泡排序。代码实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<stdio.h>
int main()
{
int a[100],i,j,t,n;
scanf("%d",&n); //输入一个数n，表示接下来有n个数
for(i=1;i<=n;i++) //循环读入n个数到数组a中
scanf("%d",&a[i]);
//冒泡排序的核心部分
for(i=1;i<=n-1;i++) //n个数排序，只用进行n-1趟
{
for(j=1;j<=n-i;j++) //从第1位开始比较直到最后一个尚未归位的数
{
if(a[j]<a[j+1]) //比较大小并交换
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
}
for(i=1;i<=n;i++) //输出结果
printf("%d ",a[i]);
getchar();getchar();
return 0;
}
假设输入为：
1
2
10
8 100 50 22 15 6 1 1000 999 0
运行结果是：
1
1000 999 100 50 22 15 8 6 1 0
将上面代码稍加修改，就可以解决第1节遗留的问题，如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<stdio.h>
struct student
{
char name[21];
int score;
}; //这里创建了一个结构体用来存储姓名和分数
int main()
{
struct student a[100],t;
int i,j,n;
scanf("%d",&n); //输入一个数n
for(i=1;i<=n;i++) //循环读入n个人名和分数
scanf("%s %d",a[i].name,&a[i].score);
//按分数从高到低进行排序
for(i=1;i<=n-1;i++)
{
for(j=1;j<=n-i;j++)
{
if(a[j].score<a[j+1].score)//对分数进行比较
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
}
for(i=1;i<=n;i++)//输出人名
printf("%s\n",a[i].name);
getchar();getchar();
return 0;
}
假设输入为：
1
2
3
4
5
6
5
huhu 5
haha 3
xixi 5
hengheng 2
gaoshou 8
运行结果是：
1
2
3
4
5
gaoshou
huhu
xixi
haha
hengheng
个人理解：其实桶排序按照这个策略也完全能解决这个问题。
3.最常用的排序-快速排序
👉相关博文：【算法基础】【排序】快速排序。
冒泡排序解决了桶排序浪费空间的问题，但在算法的执行效率上却牺牲了很多，它的时间复杂度达到了$O(N^2)$。假如我们的计算机每秒钟可以运行10亿次，那么对1亿个数进行排序，桶排序只需要0.1秒，而冒泡排序则需要1千万秒，达到115天之久。因此引入快速排序，既不浪费空间又可以速度很快。
假设待排序的数为：
1
6 1 2 7 9 3 4 5 10 8
设第一个数6为基准数。
先向左移动j（j--），直到找到一个小于6的数停下来。接下来向右移动i（i++），直到找到一个大于6的数停下来，然后交换i和j所指的数：
到此，第一次交换结束。接下来j继续向左挪动（每次必须是j先出发）。和上一次移动的规则一样：
直至i和j相遇：
这里介绍的快速排序流程和【算法基础】【排序】快速排序稍有不同，但原理都是一样的。
此时，第一轮排序结束，6左边的数都小于6，6右边的数都大于6。后续再分别对左右两个子序列进行同样规则的排序即可，迭代多次，直至所有排序完成。
快速排序的最差时间复杂度和冒泡排序是一样的，都是$O(N^2)$，它的平均时间复杂度为$O(N \log N)$。快速排序的实现代码见下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<stdio.h>
int a[101],n; //定义全局变量，这两个变量需要在子函数中使用
void quicksort(int left, int right)
{
int i,j,t,temp;
if(left>right)
return;
temp=a[left]; //temp中存的就是基准数
i=left;
j=right;
while(i!=j)
{
//顺序很重要，要先从右往左找
while(a[j]>=temp && i<j)
j--;
//再从左往右找
while(a[i]<=temp && i<j)
i++;
//交换两个数在数组中的位置
if(i<j)//当i和j没有相遇时
{
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
//最终将基准数归位
a[left]=a[i];
a[i]=temp;
quicksort(left,i-1);//继续处理左边的，这里是一个递归的过程
quicksort(i+1,right);//继续处理右边的，这里是一个递归的过程
}
int main()
{
int i,j,t;
//读入数据
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
quicksort(1,n); //快速排序调用
//输出排序后的结果
for(i=1;i<=n;i++)
printf("%d ",a[i]);
getchar();getchar();
return 0;
}
输入
1
2
10
6 1 2 7 9 3 4 5 10 8
得到的输出为：
1
1 2 3 4 5 6 7 8 9 10
4.小哼买书
一个实战例子，这里不再赘述。此处附上之前写的10种经典排序算法的博文链接（内附c++和python代码实现）：
