冒泡排序是一个很经典的面试题，每次排序都能将最大的数字排到最后，或者将最小的数字排到最前面。现在有一个问题如下：

1、问题

如果要对下面这一组数据从小到大进行排列，你肯定会说，我直接一看就能看出来，一分钟就能排出顺序来。

[75,66,33,34,31,337,65,346]

那是因为这里的数字只有8个，如果有800个呢？

所以我们得靠计算机，得用算法。

为了方便起见，我们就把这8个数字想象成800个，原理是一样的，先看看冒泡排序是怎样的思想吧。

2、冒泡排序思想

• 基本思想: 冒泡排序，类似于水中冒泡，较大的数沉下去，较小的数慢慢冒起来，假设从小到大，即为较大的数慢慢往后排，较小的数慢慢往前排。
• 直观表达，每一趟遍历，将一个最大的数移到序列末尾。

结论：每次循环从起始位置 n 与 n+1 进行对比，符合条件就互相调换。

3、基本原理

从后往前（或从前往后）两两比较相邻元素的值，若为逆序，则交换它们，直到序列比较完。称这样过程为一趟冒泡排序，最多只需n-1趟排序。 每一趟排序都可以使一个元素移动到最终位置，已经确定最终位置的元素在之后的处理中无需再对比。 如果某一趟排序过程中未发生“交换”，则算法可提前结束。

4、排序算法

冒泡排序流程图：

4.1、javascript实现代码

<script type="text/javascript">
 function maopao(array){
     var temp;
     for(var i=0;i<array.length;i++){ //比较多少趟，从第一趟开始
        for(var j=0;j<array.length-i-1;j++){ //每一趟比较多少次数
           if(array[j]>arra[j+1]){
              temp=array[j];
              array[j]=array[j+1];
              array[j+1]=temp;
           }
        }
     };
     return array;
 }

 var numbers=[65,4,43,37,31,17,6,46];
 var s=maopao(numbers);
 console.log(s);
</script>

4.2、java实现代码

java冒泡排序跟javascript冒泡排序肯定原理是相同的，不同的就是语言不同，下面就来实现java的冒泡排序。

    public static void main(String[] args) {
         int[] arr = {3,2,3,4,5};
        for (int i = 0; i < arr.length-1; i++) {
            for (int j = 0; j <arr.length-1-i; j++) {
                if (arr[j] > arr[j+1]) {
                    temp(arr, j, j+1);
                }
            }
        }
    }

在面试时能写出以上代码，基本没啥问题了，但是还有种最优的选择就是使用递归方式，把下面方式写出来，面试官会对你刮目相看的。

优化冒泡排序并测试其最好时间复杂度

冒泡排序通过循环将数组中相邻的两个值进行对比、交换已到达排序的目的。那么，对于相同长度的已排序数组和未排序数组来说，它们所消耗的时间是一样的。

5、使用递归优化冒泡排序

冒泡排序方法（下面方法默认使用从小到大有序排列的数组）

  public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length-1; i++) {
            long start = System.currentTimeMillis();
            /*
            通过递归来逐一判断是否有 arr[n] > arr[n+1] 或者 arr[n] > arr[n+1]的情况
                1.当数组为有序时，最快时间复杂度为n
                2,当数组完全无序时，时间复杂度会比普通的冒泡排序高
            */
            boolean flag = recursion(arr,i);
            long end = System.currentTimeMillis();
            System.out.println("递归所用时间："+(end-start));
             // 如果flag==true，则数组是有序的，直接结束排序方法
            if (flag) break;    
            for (int j = 0; j <arr.length-1-i; j++) {
                if (arr[j] > arr[j+1]) {
                    temp(arr, j, j+1);
                }
            }
        }
    }
    // 打印
    public static void print_b(int[] arr) {
        System.out.print("[");
        for (int i = 0; i < arr.length; i++) {
            if( i == arr.length-1 ) System.out.print(arr[i]);
            else System.out.print(arr[i] + ",");
        }        
        System.out.println("]");
    }
    // 交换
    public static void temp(int[] arr , int num1,int num2) {
        int temp  = arr[num1];
        arr[num1] = arr[num2];
        arr[num2] = temp;
    }

递归方法

1. 调用方法传递数组arr和当前数组下标n；
2. 通过递归对下标为n的值和下标为n+1 的值对比。

• 当 n == arr.length-1，即n已经到达数组最后一个值的下标时，返回true；
• 当存在 arr[n] > arr[n+1] 时返回 false 并结束方法。

 // 递归
    public static boolean recursion(int[] arr,int n ) {
        if (n == arr.length-1) {
            return true;
        }else if (arr[n] > arr[n+1] ) {
            return false;
        }
        return recursion(arr, n+1);
    }

小结

1.冒泡排序一般是通过两层循环进行处理，第一层循环主要为了让冒泡排序成功，数组需要进行多少次大循环，这里我们确定了在一个大于等于两个数字的数组时（因为只存在一个数字的数组不需要排序），确定一个数字的排序就需要一个大循环，即n个数字有n-1次大循环；第二层循环主要是将数组的第一个数字与其后面的数字进行比较，然后确定排序。

2.综上所述，在第二层循环完成的时候，第一层大循环也完成了一次，因此该数组就已经确定好了一个数字的排序在所有循环完成后，冒泡排序（数字从小到大）就完成了。

3.说白了就是1和2比，把大的放后面，2和3比，一样，大的放后面，3和4比，直到比完一圈，这样的话，最大的永远被放后面，于是就排了最后一个了，把前面的n-1个再来一遍，于是又有一个最大值，再来，最后排完了。

4.冒泡排序由于比较简单和容易理解，往往会成为面试时首先想到的排序算法问题。小伙伴如果能手写出来，完全不怕面试啦。