算法（一）之排序算法（一）——冒泡排序（BubbleSort）

冒泡排序是八大排序算法之一。其排序原理是每次都对相邻的两个数进行比较，如果前面一个数大于后面一个数，那就交换两个数的位置，这样一直循环下来就可以把最大的找到放在最后面。

如现在有一组数据：[3, 1, 8, 6, 2, 5, 9, 4, 7]

使用冒泡排序对这组数据进行排序，具体流程：

第一趟排序: 从前往后一次把相邻的两个数进行比较。

          3    1    8    6    2    5    9    4    7

（1）把3和1进行比较，3>1，把3和1交换位置

         1    3    8    6    2    5    9    4    7

（2）把3和8进行比较，3<8，则不做任何事

        1    3    8    6    2    5    9    4    7

（3）把8和6进行比较，8>6，把8和6交换位置

        1    3    6    8    2    5    9    4    7

（4）把8和2进行比较，8>2，把8和2交换位置

        1    3    6    2    8    5    9    4    7

（5）把8和5进行比较，8>5，把8和5交换位置

        1    3    6    2    5    8    9    4    7

（6）把8和9进行比较，8<9，则不做任何事

        1    3    6    2    5    8    9    4    7

（7）把9和4进行比较，9>4，把9和4交换位置

        1    3    6    2    5    8    4    9    7

（8）把9和7进行比较，9>7，把9和7交换位置

        1    3    6    2    5    8    4    7    9

第一趟排序下来，我们发现已经把最大值找到放在了最右边，那接下来我们只需要对前面8个数进行排序就可以了

第二趟排序

        1    3    6    2    5    8    4    7    9

（1）把1和3进行比较，1<3，则不做任何事

        1    3    6    2    5    8    4    7    9

（2）把3和6进行比较，3<6，则不做任何事

        1    3    6    2    5    8    4    7    9

（3）把6和2进行比较，6>2，把6和2交换位置

        1    3    2    6    5    8    4    7    9

（4）把6和5进行比较，6>5，把6和5交换位置

        1    3    2    5    6    8    4    7    9

（5）把6和8进行比较，6<8，则不做任何事

        1    3    2    5    6    8    4    7    9

（6）把8和4进行比较，8>4，把8和4交换位置

        1    3    2    5    6    4    8    7    9

（7）把8和7进行比较，8>7，把8和7交换位置

        1    3    2    5    6    4    7    8    9

经过第二趟排序，我们是不是又把一个最大值找到了，就是8，而且我们发现我们的数据越来越接近要排序之后的效果了。

而且有的时候相邻的两个数是不是之前就已经排好序了？就像第（5）步，是不是不用做任何事情。这就是冒泡排序可以在原来的基础上进行优化的地方。

而且我们的每趟排序要排序的次数都会比要排序数组的长度少1个。就像第一趟有9个数要排，我们只排序了8次；第二趟有8个数要排，我们只排序了7次。那么经过这样不停的循环，我们是不是就可以得到最终结果了。

现在直接上代码

      public static void bubbleSort(int[] array){
          for(int i = array.length-1; i>0; i--){
              boolean flag = true;    //如果是true,就证明比较的两个数据是有序的
              for(int j = 0; j<i; j++){
                  if(array[j]> array[j+1]){
                      int temp = array[j];
                      array[j] = array[j+1];
                      array[j+1] = temp;
                      flag = false;
                  }
              }
              if(flag){   //如果之前没有发生过交换，那flag就还是true，我们在这里退出可以减少排序次数
                  break;
              }
          }
      }

冒泡排序应用场景：

（1）数据量较小，在8个数以内，数据量大的话冒泡排序的性能比较差。

（2）斗牛游戏、炸金花的纸牌排序（多关键字排序，需自己定义排序规则，使用对象的compareTo接口）。

小编总结，请指出不足！

最后编辑于：2017.12.21 17:15:54