经典算法详解之冒泡排序

女爷i 2022-06-13 13:17 297阅读 0赞

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

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

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

**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

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

![1334741803_7937.png][]

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

//从左向右，左冒泡
    	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

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

![1334741987_1410.png][]

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

//冒泡排序最优算法
    	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)。

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

[1334741803_7937.png]: https://img-my.csdn.net/uploads/201204/18/1334741803_7937.png
[1334741987_1410.png]: https://img-my.csdn.net/uploads/201204/18/1334741987_1410.png