排序算法之冒泡排序

冒泡排序（Bubble Sort）

冒泡排序核心思想是重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。

算法描述

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

代码实现

public class BubbleSort {

    public static void main(String[] args) {
      int[] num = new int[]{5,4,6,2,7,3,1};
      sort(num);
    }

    public static void sort(int[] num){
        for (int i = 0; i < num.length ; i++) {
            // 外循环每完成一次，都会出现一个最大值，所以内循环的比较次数要减去i,即j < num.lengh-i-1
            for (int j = 0; j < num.length - i - 1 ; j++) {
                if (num[j] > num[j+1]) {
                   int temp = num[j];
                   num[j] = num[j+1];
                   num[j+1] = temp;
                }
            }
            for (int k : num) {
                System.out.print(k + " ");
            }
    }
}

输出结果：

4 5 2 6 3 1 7 
4 2 5 3 1 6 7 
2 4 3 1 5 6 7 
2 3 1 4 5 6 7 
2 1 3 4 5 6 7 
1 2 3 4 5 6 7 
1 2 3 4 5 6 7 

认真观察下，你会发现到了第6次的时候，已经排好了，还是继续在排，下面做个优化：

public static void improve_sort(int[] num){
        boolean flag;
        for (int i = 0; i < num.length ; i++) {
            flag = true;
            for (int j = 0; j < num.length - i - 1 ; j++) {
                if (num[j] > num[j+1]) {
                    flag = false;
                    int temp = num[j];
                    num[j] = num[j+1];
                    num[j+1] = temp;
                }
            }
            if(flag){
                break;
            }

            for (int k : num) {
                System.out.print(k + " ");
            }
        }
    }

加入了一个flag的标志，假如没有执行过交换数字的操作，就直接break掉循环。

算法分析

最佳情况：T(n) = O(n) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)

参考：
https://www.cnblogs.com/guoyaohua/p/8600214.html
http://data.biancheng.net/view/70.html