[Day15] CH10：排序大家族——气泡排序法

在「排序大家族」这个主题，会介绍几种常见的排序，也会简单分析他们的特性和演算法，第一天登场的是气泡排序法（Bubble Sort）。

昨天在二元搜寻前，要给定已排序好的阵列，那要怎麽排序呢？就像我们在玩扑克牌时，需要将牌按照大小排列一样。

气泡排序法

又称泡沫排序法，顾名思义就是像泡泡一样，越大的泡泡会越往上飘，藉此完成排序。由未排序的第一笔资料开始，若前面大於後面资料则俩俩交换位置，直到所有资料皆已由小至大排序。

给定一个阵列：

41, 24, 97,  6, 19, 53, 78

一开始，41 和 24 比大小，大的会往後放，41 > 24 所以两者需要交换位置。

24, 41, 97,  6, 19, 53, 78

接下来，比较 41 与 97，97 较大，所以不用交换。再来比较 97 和 6，97 > 6，两者交换。

24, 41,  6, 97, 19, 53, 78

一直持续这样直到最後 97 和 48 最後一次交换，此时 97 就会交换至最後一个，也就是此阵列最大的数字。

24, 41,  6, 19, 53, 78, 97

第一轮结束後，可以排序好一个数字，接下来又回到头开始比较，所以我们需要 n-1 轮（因为第 n-1 轮结束剩下最後一个未排序的数字，也就是最小的数字了！），才可以将整个阵列由小至大排序，以下动图可以和程序码一起服用：

public class BubbleSort {
    public static void main(String[] argvs){
        int[] arr = {41, 24, 97, 6, 19, 53, 78};
        int n = arr.length;
        for(int i = 0 ; i < n-1 ; i++){
            for(int j = 0 ; j < n-i-1 ; j++){
                if(arr[j] > arr[j+1]){  //两数字交换
                    int t = arr[j+1];
                    arr[j+1] = arr[j];
                    arr[j] = t;
                }
            }
        }
        for(int i = 0 ; i < n ; i++){
            System.out.printf("%d ", arr[i]);
        }
    }
}

在演算法中，我们经常讨论的是「时间复杂度」和「空间复杂度」，这个教学主要会介绍时间复杂度，在昨天已经有提到了，但还没正式介绍。

时间复杂度

可以定性描述演算法执行的时间，通常使用大 O 表示。简单来看，假设有 n 笔输入，最多需要 ，则时间复杂度就是 O()。

通常我们会看在最好、平均、最坏的三个情况下的时间复杂度。由气泡排序法来看，最好的情况就是一开始就由小到大排列，则时间复杂度为 O(1)。平均的情况是第 n 笔资料，会比较 (n-1) / 2 次，时间复杂度为 O()。最坏的情况是一开始由大排到小，总共需要执行 n(n-1) / 2 次，时间复杂度为 O()。

如果以上的演算法概念不是很懂不要紧，但是排序的原理和写法一定要搞懂哦。大家可以想想看排序还可以怎麽排呢？