冒泡排序算法的原理与实现

冒泡排序

基本思想：在待排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的俩个数依次进行比较和调整，让较大的数往下沉，较小的数往上冒。即 当相邻的俩个数比较好发现它们的排序与排序要求相反时，就将它们互换。

冒泡排序的示例：对 49 38 65 97 76 13 27 49进行冒泡演示。

初始顺序：49 38 65 97 76 13 27 49 按照从小到大冒泡

第一趟排序： 38 49 65 76 13 27 49 97
第一趟排序原理： 第一条记录49与第二条记录38比较 根据排序要求（从小到大冒泡即 小的上冒 大的下沉） 49 下沉 38 上冒 数组变成（38 49 65 97 76 13 27 49），接着用第二条记录49与第三条记录65比较，根据排序要求 数组保持原样（38 49 65 97 76 13 27 49），以此类推第。直到最后一条记录。 第一趟排序的结果是（38 49 65 76 13 27 49 97）

第二趟排序：38 49 65 13 27 49 76 97

第三趟排序：38 49 13 27 49 65 76 97

第四趟排序：38 13 27 49 49 65 76 97

由冒泡演示的示例得：冒泡每趟循环存在多个位置上的数据的变化，相邻的俩个数比较好发现它们的排序与排序要求相反时，就将它们互换，这与前面说的简单选择排序不同，简单选择排序每趟循环最多俩个位置的数互换–>即俩个位置发生变化。

基于上述的思想的一种代码实现。

@Test
     public void test1(){
         //定义待排序的数组 49,38,65,97,76,13,27,49
         int a[] ={49,38,65,97,76,13,27,49};
         //定义中间变量   用于俩个数字交换时的转换
         int tmp;
         for(int i = 0; i<a.length; i++){
             for(int j = 0;j<a.length-i-1;j++){   //j<a.length-i-1中-i可以省略，省略之后只是多比较了几次，但是-1不能省略，如果不-1，即当j=a.length，for循环中j++会越界，因此j只能-1.使j不能取到最后一条记录，此时j++能取到最后一条。
                 if(a[j]>a[j+1]){    //前一个元素>后一个  则大的下沉   小的上冒。
                     tmp = a[j];
                     a[j] = a[j+1];
                     a[j+1] = tmp;
                 }
             }
          }
         System.out.println(Arrays.toString(a));
     }

总结

1. 冒泡排序的思想就是相邻的俩个位置比较，不符合排序要求就交换位置，专业术语交上冒和下沉。
2. 冒泡排序中的交换操作相对简单选择排序来说，是比较多的

缺点：传统的冒泡排序中每一趟排序只能找到一个最大值或最小值，效率低。

我们考虑利用在每一趟排序中进行正向和反向俩遍冒泡的方法一次可以得到俩个最终值（最大值和最小值），从而使排序趟数减少了一半，就是后面要说的冒泡算法的改进。