1、相关介绍

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

2、基本实现步骤

  • 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
  • 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
  • 针对所有的元素重复以上的步骤，除了最后一个；
  • 重复步骤1~3，直到排序完成。

冒泡排序其实可以分为两种

  • 传统的冒泡排序
    • 时间复杂度均为：O(n^2)

  • 经过改进的冒泡排序

    • 最差：O(n^2)

    • 最优：O(n) —> 序列已经有序，只需经过一次遍历即可

      3、传统+优化的冒泡排序

      Java源码 ```java /**

      • 冒泡排序（升序）
      • 包括两种冒泡排序
      • 1.传统冒泡
      • 2.冒泡排序的优化
      • @author tao / public class BubbleSort {

      /**

      • 传统的冒泡排序
      • @param arr
      • @return */ public static int [] bubbleSort(int [] arr) { for(int i=0;i<arr.length-1;i++) { //外层控制循环次数
        1.  for(int j=0;j<arr.length-1-i;j++) { //内层控制每一趟排多少次  j=0:每次从第一个开始冒泡；减去i表示后端已经排好的元素的个数，就不需要进行排序了
        2.      if(arr[j]>arr[j+1]){  //利用异或法交换两数位置
        3.          int temp = arr[j];
        4.          arr[j]  =arr[j+1];
        5.          arr[j+1] =temp;
        6.      }
        7.  }
        }
        return arr; }

      /**

      • 经过优化的冒泡排序，只是在原有的逻辑上添加了didSort变量进行优化
      • @param arr

      • @return */ public static int [] bubbleSort2(int [] arr ){

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

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

         didSort = true;
     }
 } //end for2   如果没有做排序，即didSort 为false说明了：该序列已经有序了不需要再进行排序，直接返回该序列即可
 if (didSort == false) return arr;

        } return arr; }

      @Test public void bubbleSort2Test(){ int [] arr = {8,8,4,2,2,1}; int [] arr2 = {8,1,2,4}; for (int i : bubbleSort2(arr2)) {

         System.out.print(i);

      } }

} ``` 1 冒泡排序 - 图1