1.交换排序

交换排序是根据待排序列中两个元素的比较结果来确定是否进行次序交换。

交换排序的特点是：通过交换，将key值较大的元素向序列的尾部移动，将key值较小的元素向序列的头部移动。

2.冒泡排序

冒泡排序是最简单、最直接的交换排序。

冒泡排序的过程：从头到尾比较相邻的两个元素，将较小的转移到前面，较大的转移到后面。

一次起泡过程：经过了从头到尾的一趟比较，将最大的元素交换到了最后一个位置。

在一个N个元素的序列a中，经过N-1次起泡后，序列就排序完成。

第一次起泡，将a[0..N-1]中最大的元素放到了a[N-1]。

第二次起泡，将a[0..N-2]中最大的元素放到了a[N-2]。

……

第N-1次起泡，将a[0..1]中最大的元素放到了a[1]。

剩下最小的元素就是a[0]，冒泡排序完成

2.1.代码实现

冒泡排序的实现非常简单，代码如下所示：

    public void bubbleSort(Integer[] a, int size) {
        Integer tmp;
        boolean allSorted;

        for (int i = 1; i < size; i++) {
            allSorted = true;
            for (int j = 0; j < size - i; j++) {
                if (a[j + 1] < a[j]) {
                    tmp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = tmp;
                    allSorted = false;
                }
            }
            if (allSorted) {
                break;
            }
        }
    }

2.2.复杂度分析

最好的情况下，如果原始序列就是有序的，则只需要一次起泡即可完成排序。需要进行N-1次比较，时间复杂度为O(N)。

最坏的情况下，就是原始序列为逆序的，需要N-1次起泡，第i次起泡涉及N-i次比较和N-i次交换。所以时间复杂度为O(N^2)。

2.3.适用场景

冒泡排序适合原始数据大部分都是有序的场景。

冒泡排序是稳定的排序算法。

3.冒泡排序案例

如下图所示：

在7个元素的序列中，最多需要6次起泡即可完成排序。