冒泡排序详细介绍

冒泡排序详细介绍

经典算法冒泡排序，最基本的排序方法，算法如下定义：

冒泡排序算法的运作如下：（从后往前）

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3. 针对所有的元素重复以上的步骤，除了最后一个。
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

冒泡排序在Java 语言中的程序如下所示：

  public static void bubbleSort(int[] a){for(int i=0;i<a.length-1;i++)for(int j=0;j<a.length-1;j++){if(a[j]>a[j+1]){int temp=a[j];a[j]=a[j+1];a[j+1]=temp;                                                                                  }}}

下面我们进行一些详细研究，对于以下序列，我们需要按照升序进行排列

32,44,12,67,109,3,200

0 ,  1, 2, 3, 4,  5, 6

那么，我们需要将程序进行补全，如下面程序，即为补全之后的程序：

package st1;
public class Bubble
{//冒泡排序算法public static void bubbleSort(int[] a){for(int i=0;i<a.length-1;i++)for(int j=0;j<a.length-1;j++){if(a[j]>a[j+1]){int temp=a[j];a[j]=a[j+1];a[j+1]=temp;}}}//用于输出结果的方法public static void show(int [] a){for(int i=0;i<a.length;i++){System.out.print(a[i]+" ");}System.out.println();}//主方法public static void main(String[] args){int [] arr={32,44,12,67,109,3,200};show(arr);//调用显示方法bubbleSort(arr);//调用冒泡排序算法show(arr);//调用显示方法}
}

排序之后的结果如下图所示：

可以看到，完成了从小到大的排列顺序，那么，排序时具体的过程有是如何呢？

这是我们进行对程序进行修改，如下所示：

package st1;
public class Bubble
{//冒泡排序算法public static void bubbleSort(int[] a){for(int i=0;i<a.length-1;i++){System.out.println("第"+(i+1)+"次循环：");for(int j=0;j<a.length-1;j++){if(a[j]>a[j+1]){int temp=a[j];a[j]=a[j+1];a[j+1]=temp;}	 //修改点         System.out.print("["+i+" ,"+j+"  ][" );show(a);}} }//用于输出结果的方法public static void show(int [] a){for(int i=0;i<a.length;i++){System.out.print(a[i]+" ");}System.out.println();}//主方法public static void main(String[] args){int [] arr={32,44,12,67,109,3,200};
//	  show(arr);//调用显示方法bubbleSort(arr);//调用冒泡排序算法
//	  show(arr);//调用显示方法}
}

运行后结果如下所示：

第1次循环：
0 0 :32 44 12 67 109 3 200
0 1 :32 12 44 67 109 3 200
0 2 :32 12 44 67 109 3 200
0 3 :32 12 44 67 109 3 200
0 4 :32 12 44 67 3 109 200
0 5 :32 12 44 67 3 109 200
第2次循环：
1 0 :12 32 44 67 3 109 200
1 1 :12 32 44 67 3 109 200
1 2 :12 32 44 67 3 109 200
1 3 :12 32 44 3 67 109 200
1 4 :12 32 44 3 67 109 200
1 5 :12 32 44 3 67 109 200
第3次循环：
2 0 :12 32 44 3 67 109 200
2 1 :12 32 44 3 67 109 200
2 2 :12 32 3 44 67 109 200
2 3 :12 32 3 44 67 109 200
2 4 :12 32 3 44 67 109 200
2 5 :12 32 3 44 67 109 200
第4次循环：
3 0 :12 32 3 44 67 109 200
3 1 :12 3 32 44 67 109 200
3 2 :12 3 32 44 67 109 200
3 3 :12 3 32 44 67 109 200
3 4 :12 3 32 44 67 109 200
3 5 :12 3 32 44 67 109 200
第5次循环：
4 0 :3 12 32 44 67 109 200
4 1 :3 12 32 44 67 109 200
4 2 :3 12 32 44 67 109 200
4 3 :3 12 32 44 67 109 200
4 4 :3 12 32 44 67 109 200
4 5 :3 12 32 44 67 109 200
第6次循环：
5 0 :3 12 32 44 67 109 200
5 1 :3 12 32 44 67 109 200
5 2 :3 12 32 44 67 109 200
5 3 :3 12 32 44 67 109 200
5 4 :3 12 32 44 67 109 200
5 5 :3 12 32 44 67 109 200
从中挑选出部分进行分析，如下：

冒泡排序  升序  小到大

第一轮排序 交换两个数的位置  6次
        如果1>2   则交换位置  否则不交换  32,44,12,67,109,3,200
        如果2>3   则交换位置  否则不交换  32,12,44,67,109,3,200
        如果3>4   则交换位置  否则不交换  32,12,44,67,109,3,200
        如果4>5   则交换位置  否则不交换  32,12,44,67,109,3,200
        如果5>6   则交换位置  否则不交换  32,12,44,67,3,109,200
        如果6>7   则交换位置  否则不交换  32,12,44,67,3,109,200
第二轮排序   5次
        如果1>2   则交换位置  否则不交换  12,32,44,67,3,109,200
        如果2>3   则交换位置  否则不交换  12,32,44,67,3,109,200
        如果3>4   则交换位置  否则不交换  12,32,44,67,3,109,200
        如果4>5   则交换位置  否则不交换  12,32,44,3,67,109,200
        如果5>6   则交换位置  否则不交换  12,32,44,3,67,109,200

第三轮排序  4次
        如果1>2   则交换位置  否则不交换  12,32,44,3,67,109,200
        如果2>3   则交换位置  否则不交换  12,32,44,3,67,109,200
        如果3>4   则交换位置  否则不交换  12,32,3,44,67,109,200
        如果4>5   则交换位置  否则不交换  12,32,3,44,67,109,200

第四轮排序  3次
        如果1>2   则交换位置  否则不交换  12,32,3,44,67,109,200
        如果2>3   则交换位置  否则不交换  12,3,32,44,67,109,200
        如果3>4   则交换位置  否则不交换  12,3,32,44,67,109,200
    
第五轮排序  2次
        如果1>2   则交换位置  否则不交换  3,12,32,44,67,109,200
        如果2>3   则交换位置  否则不交换  3,12,32,44,67,109,200
第六轮排序  1次
        如果1>2   则交换位置  否则不交换  3,12,32,44,67,109,200

       

经过上述过程，最终实现了排序