第一章排序

第一节简化版桶排法

　　友情提示：此文章分享给所有小白，大牛请绕路！

　　

　　生活中很多地方需要使用排序，价格的由低到高、距离的由远及近等，都是排序问题的体现。如果排序量较少，依靠个人能力很容易实现；但如果排序种类多、数量大，则很难依靠脑力解决。这时就需要我们利用算法来解决问题。

　　如果你现在还没离开，那么我就认为你是和我一样不怎么懂算法的小白了。

　　你是否学习过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;

}

　　注：此专题参考于《啊哈！算法》（啊哈磊著），想要了解更多请购买正版书籍。

　　

附：诗

你是人间的四月天 ———— 一句爱的赞颂

林徽因

我说你是人间的四月天；

笑响点亮了四面风；

轻灵在春的光艳中交舞着变。

你是四月早天里的云烟，

黄昏吹着风的软，

星子在无意中闪，

细雨点洒在花前。

那轻，那娉婷，你是，

鲜妍百花的冠冕你戴着，

你是天真，庄严，

你是夜夜的月圆。

雪化后那片鹅黄，你像；

新鲜初放芽的绿，你是；

柔嫩喜悦，

水光浮动着你梦期待中白莲。

你是一树一树的花开，

是燕在梁间呢喃，

——你是爱，是暖，是希望，

你是人间的四月天！

声明：

上周差下的这周会补上，上周末好累，原谅我嘞。。。

以上。

巴特西

和我一起从0学算法（C语言版）（一）

第一章排序

第一节简化版桶排法

第二节冒泡排序

附：诗

你是人间的四月天 ———— 一句爱的赞颂

林徽因

最新文章

热门文章

巴特西

和我一起从0学算法（C语言版）（一）

第一章 排序

第一节 简化版桶排法

第二节 冒泡排序

附：诗

你是人间的四月天 ———— 一句爱的赞颂

林徽因

最新文章

热门文章

第一章排序

第一节简化版桶排法

第二节冒泡排序