经典算法之冒泡排序（简略版）

冒泡排序

算法概念

了解一个知识，必须先要从其含义开始。 冒泡排序，什么是冒泡排序，这种排序方法是通过相邻的两个元素两两比较，根据大小来交换位置，最值元素就像气泡一样从左侧向右侧移动，故名冒泡排序。冒泡排序是一种计算机科学领域的较简单基础的排序算法。其基本思路是，对于一组要排序的元素列，依次比较相邻的两个数，将比较小的数放在前面，比较大的数放在后面，如此继续，直到比较到最后的两个数，将小数放在前面，大数放在后面，重复步骤，直至全部排序完成。

举一个例子说明冒泡排序是如何排序的：水桶位置例子

现有4个水桶【A、B、C、D】，每个水桶质量各不同，现要球按照质量大小，从小到大排序。（其中大小关系为【B>D>A>C】）

现如今按照冒泡排序的排序方式进行排序。首先比较A和B的大小关系，A小于B，那么AB不需要交换位置。则继续进行B和C的比较，由B和C大小关系比较，B大于C那么，B和C交换位置，此时位置顺序为【A、C、B、D】。在由B和D，B大于D，则B和D交换位置。此时位置顺序为【A、C、D、B】。 然后进行第二轮的排序 A与C进行比较，A>C，交换A与C之间的位置，则此时的位置顺序为【C、A、D、B】。再比较A与D的关系，A小于D，则不需要交换，此时的位置顺序为【C、A、D、B】此时排序完毕，不需要再一次重复性的比较。

算法图例

第一轮比较

第二轮比较

经过两轮比较就将水桶的排序位置搞定

代码实现

采用JS来实现冒泡排序代码

定义一个数组

var arr=[6,10,12,23,43,52,58,68,70,94,128]

冒泡方法实现

 for(var i=0;i<arr.length;i++){
        for(var j=1;j<arr.length-i;j++){
            if(arr[j-1]>arr[j]){
                var temp=arr[j];
                arr[j]=arr[j-1];
                arr[j-1]=temp;
            }
        }
    }

Java实现

int [] arr = new int[]{34,5,-5,9,86,26};
		
		for(int i = 0;i < arr.length - 1;i++){
			
			for(int j = 0;j < arr.length - 1 -j;j++){
				
				if(arr[j] > arr[j+1]){
					int temp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = temp;
					
				}
			}

代码解析

外部循环，遍历循环的总次数

for(var i=0;i<arr.length;i++){
//方法体
}

内部for循环

for(var j=1;j<arr.length-i;j++){
	//方法体
}

循环匹配次数，每次匹配后减少一次循环，因为最后一个数组都是已经循环完成的，不需要重复进行。

交换代码

	if(arr[j-1]>arr[j]){
                var temp=arr[j];
                arr[j]=arr[j-1];
                arr[j-1]=temp;
            }

当元素i-1的元素大于i元素位置时，则说明不符合排序升序，需要交换元素位置。

总结

冒泡排序是经典算法中的较为简单的排序算法之一，运用较为广泛，经典之经典，推敲算法。跟着敲一遍，更有利于算法的学习。

更详细的冒泡排序请详见主页顶置的冒泡排序文章。