经典算法详解 之 冒泡排序

排序算法对程序员来说是比较基础的东西，但是因为它们比较繁琐，所以有时候就容易弄混，特别是一些算法本身就很相似的话，就更难弄清楚它们之间的区别和联系！

排序可以分为内排序和外排序，一般我们所说的排序仅指的是内排序。这次我们来分别熟悉一下内部排序中的各种排！关于内排序和外排序，本为不做重点介绍！

在说排序之前，我们先熟悉一下排序中元素互换常用的三句代码：

temp=a;

a=b;

b=temp;

这三行代码的含义是利用temp这个临时仓库交换a和b。这三句代码是比较经典的数据交换代码，可以确定的是任何语言的数据交换都可以类似的写成这个形式。当然你用的语言或者数据类型不同的话，也是需要稍微变化一下的，但是整体的思路是不会变动的。如果说不用temp这个临时仓库，写成：

a=a+b;

b=a-b;

a=a-b;

这三行代码来完成数据交换的话，那对读者来说可就不那么容易理解了，当然对一些代码特别敏感的变态除外。需要说的是：有时候数据类型之间如果不能进行加或减的运算，那么这上述三行代码可是会出报错的。

好了就下来就说一下最常用的排序——冒泡排序

为了让读者理解所谓的冒泡排序，我们概括一下冒泡排序的规则：

冒泡排序的法则是：将一串待排序的数据从一个方向依次与第一个或最后一个进行比较，将正在进行比较的两数中的较大或较小的值，换到两个数相对较前或较后的位置上来，然后将本次得到的较大或较小的值与下一个数据元素进行比较，最终将待排序序列中的最值（最大或最小值）排到最前或最后，并且该最值不再参与下一次的比较。到此为止第一趟排序结束，接着进行下一趟的排序，直到第一个或最后一个数据为止。

接下来，我们来具几个简单的例子。

例：

	public class BubbleSort{
		public static void main(String[] args){
			int[] list={0,1,2,3,4,5,6,7,8,9};
			System.out.println("Before quick sort:");
			for(int i=0;i<list.length;i++){
				System.out.print(list[i]+" ");
			}
			
			bubbleSort(list);
			
			System.out.println("\n After quick sort:");
			for(int i=0;i<list.length;i++){
				System.out.print(list[i]+" ");
			}
		}
		
		//从右向左，右冒泡
		private static void bubbleSort(int[] list){
			for(int i=list.length-1;i>0;i--){
				for(int j=i-1;j>=0;j--){
					if(list[i]>list[j]){
						int temp=list[i];
						list[i]=list[j];
						list[j]=temp;
					}
				}
			}
		}
	}

以上是我们经常写的从右向左，右冒泡的冒泡排序算法。它的规则是将一串待排序的数据从右方依次与最后一个进行比较，将正在进行比较两数中的较小的值，换到两个数相对较前的位置上来，然后将本次得到的较小的值与下一个数据元素进行比较，最终将待排序序列中的最小值排到最后，并且该最值不再参与下一次的比较。到此为止第一趟排序结束，接着进行下一趟的排序，直到第一个数据为止。

上述排序的过程得到的每一趟排序的结果如下：

原始数据：0 1 23 4 5 6 7 8 9

第1趟排序：1 2 3 4 5 6 7 8 9 0比较时间：9单位

第2趟排序：2 3 4 5 6 7 8 9 1 0比较时间：8单位

第3趟排序：3 4 5 6 7 8 9 2 1 0比较时间：7单位

第4趟排序：4 5 6 7 8 9 3 2 1 0比较时间：6单位

第5趟排序：5 6 7 8 9 4 3 2 1 0比较时间：5单位

第6趟排序：6 7 8 9 5 4 3 2 1 0比较时间：4单位

第7趟排序：7 8 9 6 5 4 3 2 1 0比较时间：3单位

第8趟排序：8 9 7 6 5 4 3 2 1 0比较时间：2单位

第9趟排序：98 7 6 5 4 3 2 1 0比较时间：1单位

最终结果：9 8 7 6 5 4 3 2 1 0

将我们上述的排序算法适当调整就得到了从左向右，右冒泡的冒泡排序算法如下所示。它的规则是将一串待排序的数据从左方依次与最后一个进行比较，将正在进行比较两数中的较小的值，换到两个数相对较前的位置上来，然后将本次得到的较小的值与下一个数据元素进行比较，最终将待排序序列中的最小值排到最后，并且该最值不再参与下一次的比较。到此为止第一趟排序结束，接着进行下一趟的排序，直到最后一个数据为止。

具体的算法如下：

	//从左向右，右冒泡
	private static void bubbleSort(int[] list){
		for(int i=0;i<list.length-1;i++){
			for(int j=0;j<list.length-1-i;j++){
				if(list[j]<list[j+1]){
					int temp=list[j];
					list[j]=list[j+1];
					list[j+1]=temp;
				}
			}
		}

	}

上述排序的过程得到的每一趟排序的结果如下：

原始数据：0 1 23 4 5 6 7 8 9

第1趟排序：1 2 3 4 5 6 7 8 90比较时间：9单位

第2趟排序：2 3 4 5 6 7 8 91 0比较时间：8单位

第3趟排序：3 4 5 6 7 8 92 1 0比较时间：7单位

第4趟排序：4 5 6 7 8 9 3 2 1 0 比较时间：6单位

第5趟排序：5 6 7 8 94 3 2 1 0比较时间：5单位

第6趟排序：6 7 8 95 4 3 2 1 0比较时间：4单位

第7趟排序：7 8 96 5 4 3 2 1 0比较时间：3单位

第8趟排序：8 97 6 5 4 3 2 1 0比较时间：2单位

第9趟排序：98 7 6 5 4 3 2 1 0比较时间：1单位

最终结果：9 8 7 6 5 4 3 2 1 0

上述两种右冒泡算法对比之后我们可以得到下面所示的这样一个三角形，它表示的含义就是参与排序的数据数量越来越小，最值就像气泡一样浮动到最右方。

当然我们也可以该动成：从左向右，左冒泡；从右向左，左冒泡。具体算法如下：

	//从左向右，左冒泡
	private static void bubbleSort(int[] list){
		for(int i=0;i<list.length-1;i++){
			for(int j=i+1;j<list.length;j++){
				if(list[i]<list[j]){
					int temp=list[i];
					list[i]=list[j];
					list[j]=temp;
				}
			}
		}
	}
	
	//从右向左，左冒泡
	 private static void bubbleSort(int[] list){
		for(int i=0;i<list.length-1;i++){
			for(int j=list.length-1;j>i;j--){
				if(list[j]>list[j-1]){
					int temp=list[j];
					list[j]=list[j-1];
					list[j-1]=temp;
				}
			}
		}
	}

上述两种左冒泡得到的结果如下：

原始数据：0 1 23 4 5 6 7 8 9

第1趟排序：9 0 1 2 3 4 5 6 7 8比较时间：9单位

第2趟排序：9 8 0 1 2 3 4 5 6 7比较时间：8单位

第3趟排序：9 8 7 0 1 2 3 4 5 6比较时间：7单位

第4趟排序：9 8 7 6 0 1 2 3 4 5比较时间：6单位

第5趟排序：9 8 7 6 5 0 1 2 3 4比较时间：5单位

第6趟排序：9 8 7 6 5 4 0 1 2 3比较时间：4单位

第7趟排序：9 8 7 6 5 4 3 0 1 2比较时间：3单位

第8趟排序：9 8 7 6 5 4 3 2 0 1比较时间：2单位

第9趟排序：9 8 7 6 5 4 3 2 1 0比较时间：1单位

最终结果：9 8 7 6 5 4 3 2 1 0

上述两种左冒泡算法对比之后我们也可以得到下面所示的这样一个三角形，它表示的含义就是参与排序的数据数量越来越小，最值就像气泡一样浮动到最左方。

接下再来我们再来介绍一个冒泡排序的最优算法。具体算法如下：

	//冒泡排序最优算法
	private static void bubbleSort(int[] list){
		boolean flag=false;//用于标识是否需要再次比较
		for(int i=0;i<list.length-1;i++){
			for(int j=0;j<list.length-1;j++){
				if(list[j]<list[j+1]){
					int temp=list[j];
					list[j]=list[j+1];
					list[j+1]=temp;
					flag=true;
				}
			}
			if(!flag)break;
		}
	}

上述算法的规则是从左向右，相邻的数进行比较交换，将最值移动到最右。当然如果读者又兴趣也可以自己写一个从右向左，相邻的数进行比较 交换，将最值移动到最左的冒泡排序算法。上述算法得到结果如下：

原始数据：0 1 23 4 5 6 7 8 9

第一趟排序结果：0 1 2 3 4 5 6 7 8 9比较时间：9单位

最终结果：0 1 23 4 5 6 7 8 9

对比一下最优算法和之前的四种排序，我们可以清楚的明白最优算法的好处，就是添加一个标识，用于记录是否需要进行第二趟的比较。这种算法从时间上来说，可以节省不必要的比较时间，当然最好时间是有条件的，即所做的排序序列已经是最终结果。

我们做个总结就可以得出这样一个结论：对于n个数比较从时间复杂度上来最好情况为O(n)，而之前讲的四种时间复杂度我们可以很容易根据（9+8+7+6+5+4+3+2+1）这种规律，得出每趟所需时间n-i（n表示数据元素的个数，i表示第几趟），所需时间总和为n*（n-1）/2,即最坏情况下时间复杂度O(n2)。

到这里，我们的冒泡排序的规律基本已经解释清楚了，接下来就需要读者做更多的思考和实践了！