冒泡排序

冒泡排序就是让小的数组元素像水中的气泡一样逐渐上浮，或者大的数组元素逐渐下沉，从而达到排序的目的。在冒泡排序中，数组被分为“已排序部分”和“未排序部分”，将“未排序部分”中小的数组元素上浮，直到所有元素有序。

具体流程：

• 重复执行下述处理，直到数组中不包含顺序相反的相邻元素
  1. 从数组末尾开始依次比较相邻两个元素，如果大小关系相反则交换位置，直到比较到“未排序部分”的第一个元素。“已排序部分”元素增加1。

以数组{5, 3, 2, 4, 1}为例使用冒泡排序，流程如下图所示：

参考代码如下：

import java.util.Arrays;

public class BubbleSort {

    public static void bubbleSort(int[] num){
        if (num==null)
            return;

        for (int i=0; i<num.length-1; i++){ //遍历的趟数 n-1，每遍历一次就有一个数在规定的位置上
            boolean flag = true;  //判断是否已经排好序了，如果排好了，直接退出循环，优化部分

            // 从后向前开始冒泡。因为前i个元素已经为排好序的，所以判断范围为i到n-1，即比较到i+1和i为止，j到i+1。
            for (int j=num.length-1; j>i; j--){
                if (num[j] < num[j-1]){
                    int temp = num[j];
                    num[j] = num[j-1];
                    num[j-1] = temp;
                    flag = false; //如果有交换，说明并没有拍好序，继续下一趟排序。
                }
            }

            if (flag)
                break;
        }
    }

    public static void main(String[] args) {

        int[] num = new int[]{3,1,5,7,2,4,9,6};
        bubbleSort(num);
        System.out.println(Arrays.toString(num));
    }
}

冒泡排序法算法稳定；时间复杂度最好情况下为O(n)，此时序列本身有序；最坏时间复杂度为O(n^{2)；平均时间复杂度为O(n}2)；空间复杂度为O(1)。