排序——冒泡排序

今天讲一下最基本的排序方法——冒泡排序。

基本思想:每次比较两个相邻的元素,如果它们的顺序错误就把它们交换过来。

例如我们需要将一组数据1 67 87 22 0,由小到大排列。即:越大的越往后。

首先,将第一位的和 67比较,发现67 比1 大,所以不用交换,之后在比较6787作比较,与前面同理,因为大的刚好在后面,所以不用交换。在将87 和 22比较,发现后一位小于前一位,所以将它俩交换,交换后的顺序是:1 67 22 87 0。在进行最后一次比较87 和 0,0 比 87 小,故交换得:1 67 22 0 87

所以经过4次比较后,我们将最大的放在了最后了。每将一个数归位我们将其称为“一趟”。

我们再试试将第二大的放在87前面,重复之前的步骤,首先比较1 和 67,不用交换,比较 67 22,交换得:1 22 67 0 87。比较67 0,交换得:1 22 0 67 87

我们比较一下第一趟和第二趟,发现了第二趟比第一趟少了一次比较,很明显是因为第一趟已经将最大的放在了最后面,所以第二趟会少一次比较,以此类推,第三趟比第二趟少一次……

总结:如果有 n 个数进行排序, 只需将 n-1 个数归位,也就是要进行 n-1 趟操作。而“每一趟”都需要从第一位开始进行相邻两个数的比较,若前一位大于后一位,完成交换即可,如无需交换,进行下次比较,一直重复此操作,直到第 n-1 次,此时该 n 个数已经完成排序。

ps:我只是以从小到大为例,当然冒泡是可以从大到小排序的,类比一下即可。

图解:

排序——冒泡排序C语言代码:

#include <stdio.h>

int main(void)
{
	int a[100];
	int i, j, t, n;
	
	scanf("%d", &n);   //输入一个数n,表示待排序数的个数
	
	for (i = 0; i < n; i++)  //读入待排序的n个数 
	{
		scanf("%d", &a[i]);
	} 
	
	/* 排序核心 */
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n - i - 1; j++)
		{
			if (a[j] > a[j+1])
			{
				t = a[j];
				a[j] = a[j+1];
				a[j+1] = t;
				
			}
		}
	}
	 
	for (i = 0; i < n; i++)  //输出结果 
	{
		printf("%d ", a[i]);
	} 

	return 0; 
} 

上一篇:1038 Recover the Smallest Number (30 分)


下一篇:益聚星荣:茶颜悦色关闭87家店,网友喊加油,公司回应:我们还撑得住