(一)排序解析

1. 原理

冒泡排序就是依次比较一个序列中相邻的两个数据大小，通过不断地交换数据的位置来将最大或者最小的数据依次交换到最后面的位置，从而达到数据排序的排序方法。

<mark>排序过程</mark> 例如：{ 3 1 2 0 }

第一轮：(将3交换到最后位置)
	比较(3>1)	交换{ 1 3 2 0 }
	比较(3>2)	交换{ 1 2 3 0 }
	比较(3>0)	交换{ 1 2 0 3 }
第二轮：(将2交换到3前面)
	比较(1<2)	不交换
	比较(2>0)	交换{ 1 0 2 3 }
第三轮：(将1交换到2前面)
	比较(1>0)	交换{ 0 1 2 3 }
排序完毕

2. 源代码

#include<stdio.h>
#define N 10
int main()
{
	int i,j,temp;
	int num[N]={9,8,7,6,5,4,3,2,1,0};
	for(i=0;i<N;i++)//循环的轮次
		for(j=0;j<N-i-1;j++)//每比较完一轮，即排好了一个数据，就相应的减少一次比较次数（N-i-1）
			if(num[j]>num[j+1])//比较相邻的数据大小
			{
				temp=num[j];//交换
				num[j]=num[j+1];
				num[j+1]=temp;
			}
	for(i=0;i<N;i++)
		printf("%d ",num[i]);
	printf("\n");
	return 0;
}

(二)算法优化

1. 优化（1）

优化思路

<mark>如下序列：</mark>

{ 9 0 1 2 3 4 5 6 7 8}//从小到大排序

<mark>根据冒泡的过程可知，当我们进行完第一轮比较交换后，序列正好排好顺序：</mark>

{ 0 1 2 3 4 5 6 7 8 9 }

此刻我们完全可以退出循环，完全不需要第三轮及以后的比较判断过程，因为当序列长度长达几万或者十几万的时候，显然多余的比较将会浪费很多时间。

<mark>优化过程：</mark>

设立一个flag，flag=1代表该轮次发生了交换，flag=0代表没有发生交换，以上序列当进行完第二轮后判断flag=0，我们就用break退出for循环。

源代码

#include<stdio.h>
#define N 10
int main()
{
	int i,j,temp,flag,count=0;
	int num[N]={9,0,1,2,3,4,5,6,7,8};
	for(i=0;i<N;i++)
	{
		flag=0;//每轮都默认没有发生交换
		for(j=0;j<N-i-1;j++)		
			if(num[j]>num[j+1])
			{
				temp=num[j];
				num[j]=num[j+1];
				num[j+1]=temp;
				flag=1;//发生交换
			}
		count++;//记录交换轮次
		if(flag==0)//当没有发生交换时就退出循环
			break;
	}
	printf("比较轮次:%d\n",count);
	for(i=0;i<N;i++)
		printf("%d ",num[i]);
	return 0;
}

2.优化（2）

优化思路

<mark>如下序列:</mark>

{ 3 2 0 1 4 5 6 7 8 9}//从小到大排序

<mark>根据冒泡的过程可知，当我们进行完第一轮比较交换后</mark>

{ 2 0 1 3 4 5 6 7 8 9 }

我们发现原序列的后半部分是已经排好顺序了，所以在第二轮比较中，2没必要和4、5、6、7、8、9 再进行多余的比较

<mark>优化过程</mark>

用flag代表比较的轮次，k代表该每一轮的比较次数，该优化过程就是在每一轮次中都更新轮次flag的值，不断缩小冒泡排序原始轮次范围N，从而达到排序的最大效率，避免不必要的比较。

源代码

#include<stdio.h>
#define N 10
int main()
{
	int num[N]={3,0,1,2,4,5,6,7,8,9};
	int i,j,k,temp,count=0;
	int flag=N;//默认比较轮次为N轮
	while(flag>0)
	{
		k=flag;//用k记录每一轮的比较次数
		flag=0;//while循环结束条件，避免产生死循环,相当于优化1过程
		for(j=0;j<k;j++)		
			if(num[j]>num[j+1])
			{
				temp=num[j];
				num[j]=num[j+1];
				num[j+1]=temp;
				flag=j+1;//记录符合交换条件的最终位置
			}
		if(flag)
			count++;//记录比较轮次
	}
	printf("比较轮次:%d\n",count);
	for(i=0;i<N;i++)
		printf("%d ",num[i]);
	printf("\n");
	return 0;
}

(三)总结

• 冒泡排序的时间复杂度我们不难得出最好的情况是O(n)，最坏的情况是O(n^2)
• 所有我们之所以进行算法优化，就是为了让时间复杂度尽量逼近于最好的情况。

<mark>就以上冒泡排序三种方法，我们可以用序列分别比较一下各自的效率</mark>

序列1：{9 8 7 6 5 4 3 2 1 0}//从小到大排序
三种方法都是进行9轮次比较
	第1轮:9次
	第2轮:8次
	第3轮:7次
	第4轮:6次
	第5轮:5次
	第6轮:4次
	第7轮:3次
	第8轮:2次
	第9轮:1次
	第10轮:0次
共计：45次if判断
这是最坏的情况

序列2：{ 3 2 0 1 4 5 6 7 8 9}//从小到大排序
原始方法：
	共10轮
	共计：45次if判断
优化方法1：
  	共3轮
		第一轮：9次
		第二轮：8次
		第三轮：7次
  	总计：24次if判断
  	
优化方法2：
	共3轮
		第一轮：9次
		第二轮：2次
		第三轮：1次
  	总计：11次if判断
  	
序列3：{ 0 1 2 3 4 5 6 7 8 9}//从小到大排序
原始方法：9轮次，共计45次if判断
优化方法1:1轮次，共计9次if判断
优化方法2:1轮次，共计9次if判断
这是最好的情况

通过以上三种序列的三种冒泡排序方法中我们不难看出优化的重要性，当序列长达几万甚至几十万的时候，判断一万次和多余判断几十万次所浪费的时间是极大的