转载

Java冒泡排序算法实例分析

对于一些基础的算法理解一致不是很透彻。以冒泡算法为例，Java实现，每次复习后，过段时间总是遗忘，又要重新看，今天索性静下心来详细分析一下，虽然是最基础的算法，然而小算法中未必没有大智慧，供本人及后来人参考。

先来看一个最笨的排序：

public static void sort1(int[] a){

int count = 0 ;

for(int i=0; i<a.length; i++){

for(int j=0; j<a.length; j++){

count++ ;if(a[i] < a[j]){

int temp = a[i];

a[i] = a[j] ;

a[j] = temp ;

}

System.out.println("#sort1 forloop count - " + count);

}

这是一种比较笨的排序方法，很多新人在写排序的时候，可能这样写理解会比较直观一些，将数组循环length*length次，所有值俩俩进行一次对比，最后得出结论：

public static void main(String[] args) {

int[] arr = new int[]{12,4,54,57,87,3,41,1,3,4,1,3,4,31,2} ;

sort1(arr);

System.out.println("最终结果：" + Arrays.toString(arr));

}

结果：

#sort1 forloop count - 225

最终结果：[1, 1, 2, 3, 3, 3, 4, 4, 4, 12, 31, 41, 54, 57, 87]

可见本次执行225次循环；

再来看一个升级版：

public static void sort2(int[] a){

int count = 0 ;

for(int i=0; i<a.length; i++){

for(int j=0; j<a.length-1; j++){

count++ ;

if(a[j] > a[j+1]){

int temp = a[j] ;

a[j] = a[j+1] ;

a[j+1] = temp ;

}

System.out.println("#sort2 forloop count - " + count);

}

本方法对上一个方法进行了进一步的简化，第一层同样循环length次，而第二层循环了length-1次，同时比较只存在于第二层循环中，由于第二层的比较重，将当前下标与当前下标+1进行比较，所以总的循环数需要length-1，否则会造成数组越界，这一种算法比较常见，甚至一些培训机构对学生进行培训时也是使用这种排序算法（至于是老师水平问题还是老师考虑到学生理解能力问题采用本种方法不得而知），本方法对第二层的循环进行了-1操作，总排序次数当然要少于第一种。

执行：

int[] arr = new int[]{12,4,54,57,87,3,41,1,3,4,1,3,4,31,2} ;

sort2(arr);

System.out.println("最终结果：" + Arrays.toString(arr));

结果：

#sort2 forloop count - 210

最终结果：[1, 1, 2, 3, 3, 3, 4, 4, 4, 12, 31, 41, 54, 57, 87]

本次执行210次循环，排序结果同第一种方法，效率有所提升。

对于大学没有学过算法和数据结构相关课程，又是初入开发行业的童鞋来说，本种算法可能需要分析一下才能明白原理。

我们来分析一下第二种方法的缺陷。

先看第二层循环：

每次循环，都要将第N个数与第N+1个数进行比较，如果第N个数大，则互换位置。例如：

数组：{12,4,54,3,22,53}

第一次循环，j=0，则比较12与4的大小，发现12>4，则互换12与4的位置，结果如下：

{4,12,54,3,22,53}

第二次循环，j=1，此次比较12与54的大小，发现12<54，则保持不动，结果如下：

{4,12,54,3,22,53}

第三次循环，j=2，比较54和3大小，54>3，则互换，结果如下：

{4,12,3,54,22,53}

第四次循环，j=3，比较54和22大小，54>22，互换，结果如下：

{4,12,3,22,54,53}

最后一次循环，j=4，比较54和53大小，54>53，互换，结果如下：

{4,12,3,22,53,54}

我们发现，每一次 i 循环，都可以将arr[length-1-i]这个位置的数选举而出，也就是说，整个循环只需要length-1次（最后一轮不用排序，因为剩下的最后一个数肯定是最小值），即可完成所有数的排序，所以第二个方法可进行进一步优化：

public static void sort2_up(int[] a){

int count = 0 ;

for(int i=0; i<a.length-1; i++){

for(int j=0; j<a.length-1; j++){

count++ ;

if(a[j] > a[j+1]){

int temp = 0 ;

temp = a[j] ;

a[j] = a[j+1] ;

a[j+1] = temp ;

}

System.out.println("#sort2_up forloop count - " + count);

}

执行：

int[] arr = new int[]{12,4,54,57,87,3,41,1,3,4,1,3,4,31,2} ;

sort2_up(arr);

System.out.println("最终结果：" + Arrays.toString(arr));

结果：

#sort2_up forloop count - 196

最终结果：[1, 1, 2, 3, 3, 3, 4, 4, 4, 12, 31, 41, 54, 57, 87]

那么现在我们来看一下冒泡排序。

以上方法，第一层循环length-1次已经没有问题，那么来看下第二层循环。

每一次我们比较第j个元素和第j+1个元素，但是仔细分析，其实还是有无效比较，我们先把sort2_up中的每一次外层循环结果打印一下看看过程：

public static void sort2_up(int[] a){

int count = 0 ;

for(int i=0; i<a.length-1; i++){

for(int j=0; j<a.length-1; j++){

count++ ;

if(a[j] > a[j+1]){

int temp = 0 ;

temp = a[j] ;

a[j] = a[j+1] ;

a[j+1] = temp ;

}

System.out.println("#sort2_up i="+i+", result: " + Arrays.toString(a));

}

System.out.println("#sort2_up forloop count - " + count);

}

#sort2_up i=0, result: [4, 12, 54, 57, 3, 41, 1, 3, 4, 1, 3, 4, 31, 2, 87]

#sort2_up i=1, result: [4, 12, 54, 3, 41, 1, 3, 4, 1, 3, 4, 31, 2, 57, 87]

#sort2_up i=2, result: [4, 12, 3, 41, 1, 3, 4, 1, 3, 4, 31, 2, 54, 57, 87]

#sort2_up i=3, result: [4, 3, 12, 1, 3, 4, 1, 3, 4, 31, 2, 41, 54, 57, 87]

#sort2_up i=4, result: [3, 4, 1, 3, 4, 1, 3, 4, 12, 2, 31, 41, 54, 57, 87]

#sort2_up i=5, result: [3, 1, 3, 4, 1, 3, 4, 4, 2, 12, 31, 41, 54, 57, 87]

#sort2_up i=6, result: [1, 3, 3, 1, 3, 4, 4, 2, 4, 12, 31, 41, 54, 57, 87]

#sort2_up i=7, result: [1, 3, 1, 3, 3, 4, 2, 4, 4, 12, 31, 41, 54, 57, 87]

#sort2_up i=8, result: [1, 1, 3, 3, 3, 2, 4, 4, 4, 12, 31, 41, 54, 57, 87]

#sort2_up i=9, result: [1, 1, 3, 3, 2, 3, 4, 4, 4, 12, 31, 41, 54, 57, 87]

#sort2_up i=10, result: [1, 1, 3, 2, 3, 3, 4, 4, 4, 12, 31, 41, 54, 57, 87]

#sort2_up i=11, result: [1, 1, 2, 3, 3, 3, 4, 4, 4, 12, 31, 41, 54, 57, 87]

#sort2_up i=12, result: [1, 1, 2, 3, 3, 3, 4, 4, 4, 12, 31, 41, 54, 57, 87]

#sort2_up i=13, result: [1, 1, 2, 3, 3, 3, 4, 4, 4, 12, 31, 41, 54, 57, 87]

#sort2_up forloop count - 196

最终结果：[1, 1, 2, 3, 3, 3, 4, 4, 4, 12, 31, 41, 54, 57, 87]

那么我们来看下内层循环，也就是j层循环：

每一次对第j个元素和第j+1个元素进行比较，循环length-1次。

问题出在循环length-1次上，为什么呢，因为从结果我们可以看到，其实每一轮都已经选出了一个最大值，比如第i=0次循环，选出了一个最大值，第i=1次循环，选出了除上一次最大值之外的最大值，以此类推。

也就是说，j层循环中，每次循环，后面的比较完全是多余的，多比较了多少次呢？答案是 i 次。

第一轮循环，也就是i=0，此时需要在内层比较所有元素大小，最终选举出一个最大值；当第二轮循环时，i=1，最大值已经选举出，此时已没有必要再进行最后一轮j循环，j循环层只需要执行length-1-i次即可，以此类推。

这就是冒泡循环的思想，每一轮循环，冒泡选出一个最大值，放到末尾：

public static void bubbleSort(int[] arr) {

int count = 0 ;

System.out.println("待排序数组：" + Arrays.toString(arr));

for (int i=0;i<arr.length-1;i++) {

for (int j=0;j<arr.length-1-i;j++) {

count++ ;

if (arr[j]>arr[j+1]) {

int temp = arr[j] ;

arr[j] = arr[j+1] ;

arr[j+1] = temp ;

}

System.out.println("第" + (i+1) + "次排序结果：" + Arrays.toString(arr));

}

System.out.println("#bubbleSort forloop count - " + count);

}

执行一下：

int[] arr = new int[]{12,4,54,57,87,3,41,1,3,4,1,3,4,31,2} ;

bubbleSort(arr);

System.out.println("最终结果：" + Arrays.toString(arr));

结果：

待排序数组：[12, 4, 54, 57, 87, 3, 41, 1, 3, 4, 1, 3, 4, 31, 2]

#第1次排序结果：[4, 12, 54, 57, 3, 41, 1, 3, 4, 1, 3, 4, 31, 2, 87]

#第2次排序结果：[4, 12, 54, 3, 41, 1, 3, 4, 1, 3, 4, 31, 2, 57, 87]

#第3次排序结果：[4, 12, 3, 41, 1, 3, 4, 1, 3, 4, 31, 2, 54, 57, 87]

#第4次排序结果：[4, 3, 12, 1, 3, 4, 1, 3, 4, 31, 2, 41, 54, 57, 87]

#第5次排序结果：[3, 4, 1, 3, 4, 1, 3, 4, 12, 2, 31, 41, 54, 57, 87]

#第6次排序结果：[3, 1, 3, 4, 1, 3, 4, 4, 2, 12, 31, 41, 54, 57, 87]

#第7次排序结果：[1, 3, 3, 1, 3, 4, 4, 2, 4, 12, 31, 41, 54, 57, 87]

#第8次排序结果：[1, 3, 1, 3, 3, 4, 2, 4, 4, 12, 31, 41, 54, 57, 87]

#第9次排序结果：[1, 1, 3, 3, 3, 2, 4, 4, 4, 12, 31, 41, 54, 57, 87]

#第10次排序结果：[1, 1, 3, 3, 2, 3, 4, 4, 4, 12, 31, 41, 54, 57, 87]

#第11次排序结果：[1, 1, 3, 2, 3, 3, 4, 4, 4, 12, 31, 41, 54, 57, 87]

#第12次排序结果：[1, 1, 2, 3, 3, 3, 4, 4, 4, 12, 31, 41, 54, 57, 87]

#第13次排序结果：[1, 1, 2, 3, 3, 3, 4, 4, 4, 12, 31, 41, 54, 57, 87]

#第14次排序结果：[1, 1, 2, 3, 3, 3, 4, 4, 4, 12, 31, 41, 54, 57, 87]

#bubbleSort forloop count - 105

最终结果：[1, 1, 2, 3, 3, 3, 4, 4, 4, 12, 31, 41, 54, 57, 87]

冒泡排序的思想，说直白点就是每次冒泡选出最大值，并且每次选出的最大值不参与下次排序。

冒泡排序的进一步优化：

上面的冒泡排序算法确实已经很高效了，但是我们仔细看输出结果，第12次、13次、14次，其排序结果相同，也就是说，实际到第12次排序已经完成，13、14次为无效操作。我们加个标记，对过程进行进一步优化：

public static void bubbleSort_up(int[] arr) {

int count = 0 ;

System.out.println("待排序数组：" + Arrays.toString(arr));

for (int i=0;i<arr.length-1;i++) {

boolean isComplete = true ;

for (int j=0;j<arr.length-1-i;j++) {

count++ ;

if (arr[j]>arr[j+1]) {

int temp = arr[j] ;

arr[j] = arr[j+1] ;

arr[j+1] = temp ;

if (isComplete)

isComplete = false ;

}

System.out.println("#第" + (i+1) + "次排序结果：" + Arrays.toString(arr));

if (isComplete)

break;

}

System.out.println("#bubbleSort_up forloop count - " + count);

}

我们每一次外层循环开始时，记录一个完成排序标记，如果内层循环有变动，则标记为false，否则为true，看结果：