第一章 排序
第一节 简化版桶排法
友情提示：此文章分享给所有小白，大牛请绕路！
生活中很多地方需要使用排序，价格的由低到高、距离的由远及近等，都是排序问题的体现。如果排序量较少，依靠个人能力很容易实现；但如果排序种类多、数量大，则很难依靠脑力解决。这时就需要我们利用算法来解决问题。
如果你现在还没离开，那么我就认为你是和我一样不怎么懂算法的小白了。
你是否学习过C语言？请继续：请学习C语言后再回来；
还没有离开？！那么说明你看懂了上面表达式，问题正式开始。
问题：在一次评比过程中，五位同学分别得到了评委老师的不同评分（满分为１０分）：５分，２分，７分，９分，７分。请你将五个分数按从小到大排序。
思路：满分为１０分，则我们可以创建０－１０，共１１个数组来分别存储这１１种不同的分数的个数。先初始化１１个数组值都为０，再遍历每个人的分数，读取到该分数后，该分数对应数组值加１。遍历完成后，按数组下标从小到大输出数组值。
程序示例：
#include<stdio.h>
#define n 5 // 宏定义常量n等于5
int main() {
int a[11],i,j,t;
for (i=0;i<=10;i++)
a[i]=0; // 初始化为0
for (i=1;i<=n;i++) { // 循环读入5个数
scanf("%d",&t); // 把每一个数读到变量t中
a[t]++;
}
for (i=0;i<=10;i++) // 循环输出数组非0值
for (j=1;j<=a[i];j++)
printf("%d",i);
return 0;
}
试想 如果排序方式为从大到小，则如何修改程序。
第二节 冒泡排序
接上一节，如果我们在从小到大排序时，要求输出该分数对应的名字，则不能利用桶排法进行排序。这时为了解决这个问题，我们需要利用新的算法来完成该操作。我希望读者可以跟着我的思路一起创造这个算法，尽管这种算法早就被人所创造，但利用创造的思路来思考问题，可以培养我们思考的能力，来创造真正没人想到过的东西。博主能力有限，不足之处请指出，谢谢！
现在，大家来思考一个问题，如果我们要对几个蚂蚁巢穴中蚂蚁的数量经行排序（先不考虑统计个数的问题），那么桶排法显然是不行的，有数以万记的蚂蚁，就要创建数以万记的数组，是对内存极大的浪费。一个好的算法是可以在最短时间里，利用最小内存等来解决问题的。
不知道大家曾经是否观察过水与植物油的分层现象，无论是先加油、还是先加水，最终在上层的一定是黄色的植物油，下层一定是透明的水。简单的物理学，告诉我们，植物油的密度小于水的密度，所以，相对较轻的植物油漂浮在水面上。
根据这个例子，我们可以想到：在从小到大排序中，比较相邻两个数的大小。如果前一个数大于后一个数，则互换这两个数的位置；否则，不做处理。这样第一次从第一个数据开始，逐个比较至最后一个数据时，最后一个数据一定为此组数据的最大值。然后第二次从第一个数据开始，逐个比较至倒数第二个数据时，此数组倒数第二个数据也一定为此组数据第二大值。第三次...
程序示例：
#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;i++) //n个数排序，只需经行n-1次
for (j=1;j<=n-i;j++)
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]);
return 0;
}
对此程序经行改造，就可以按评分的从小到大顺序，输出名字。如以下：
程序示例：
#include<stdio.h>
struct student {
char name[10];
int score;
}; // 创建一个结构体用来储存姓名和分数
int main() {
struct student a[100],t;
int i,j,n;
scanf("%d",&n); // 输入一个数n，表示接下来将会输入n个数
for (i=1;i<=n;i++) // 循环读入n个数到数组a中
scanf("%s %d",a[i].name,&a[i].score);
for (i=1;i<n;i++) //n个数排序，只需经行n-1次
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 ",a[i].name);
return 0;
}
注：此专题参考于《啊哈！算法》（啊哈磊 著），想要了解更多请购买正版书籍。
附：诗
你是人间的四月天 ———— 一句爱的赞颂
林徽因
我说 你是人间的四月天；
笑响点亮了四面风；
轻灵在春的光艳中交舞着变。
你是四月早天里的云烟，
黄昏吹着风的软，
星子在无意中闪，
细雨点洒在花前。
那轻，那娉婷，你是，
鲜妍百花的冠冕你戴着，
你是天真，庄严，
你是夜夜的月圆。
雪化后那片鹅黄，你像；
新鲜初放芽的绿，你是；
柔嫩喜悦，
水光浮动着你梦期待中白莲。
你是一树一树的花开，
是燕在梁间呢喃，
——你是爱，是暖，是希望，
你是人间的四月天！
声明：
上周差下的这周会补上，上周末好累，原谅我嘞。。。
以上。