排序算法（一）冒泡排序

一 .算法的基本思路
1. 从一组元素的最左边开始，比较0号位置和1号位置的元素，如果左边的元素（0号）大，就交换这两个数；如果右边的元素（1号）大，就什么也不做。然后比较1号位置和2号位置的元素，和刚才一样，如果左边的元素大，就交换两个数。
2. 沿着这组元素照刚才那样比较下去，一直比较到这组元素的最右边。虽然还没有完全把所有元素都排好序，但是最大的元素已经被排在了最右边。在对所有的元素进行了第一趟排序之后，进行N-1次比较，并且按照元素的初始位置，进行最少0次，最多N-1次的交换。元素最末端的那个数据项就此排定，不需要再移动了。
3. 现在重新回到元素的最左端开始进行第二趟排序，再一次的从左到右，两两比较，并且在适当的时候交换元素的位置，这一次只需比较到右边第二个元素（位置N-2）。不断执行这个过程，直到所有元素都排定。

---

二. 示例说明
初始元素： 8 2 16 9 7 4 6
第一趟排序： 2 8 9 7 4 6 16 （第一趟排序，比较6次，16沉到未排序尾部）
第二趟排序： 2 8 7 4 6 9 16（第二趟排序，比较5次，9沉到未排序尾部）
第三趟排序： 2 7 4 6 8 9 16（第三趟排序，比较4次，8沉到未排序尾部）
第四趟排序： 2 4 6 7 8 9 16（第四趟排序，比较3次，7沉到未排序尾部）
第五趟排序： 2 4 6 7 8 9 16（第五趟排序，比较2次，6沉到未排序尾部）
第六趟排序： 2 4 6 7 8 9 16（第六趟排序，比较1次，4沉到未排序尾部）
N个数字要排序完成，总共进行N-1趟排序，每i趟的排序次数为(N-i)次，所以可以用双重循环语句，外层控制循环多少趟，内层控制每一趟的循环次数。
三. 算法实现

public class BubbleSort {

    public static void bubbleSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int e = arr.length - 1; e > 0; e--) {
            for (int i = 0; i < e; i++) {
                if (arr[i] > arr[i + 1]) {
                    swap(arr, i, i + 1);
                }
            }
        }
    }

    public static void swap(int[] arr, int i, int j) {
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }

四.时间复杂度、空间复杂度与稳定性
1.时间复杂度

当原始序列“正序”排列时，冒泡排序总的比较次数为n-1，移动次数为0，也就是说冒泡排序在最好情况下的时间复杂度为O(n)；

当原始序列“逆序”排序时，冒泡排序总的比较次数为n(n-1)/2，移动次数为3n(n-1)/2次，所以冒泡排序在最坏情况下的时间复杂度为O(n^2)；

当原始序列杂乱无序时，冒泡排序的平均时间复杂度为O(n^2)。

2.空间复杂度

冒泡排序排序过程中需要一个临时变量进行两两交换，所需要的额外空间为1，因此空间复杂度为O(1)。

3.稳定性

冒泡排序在排序过程中，元素两两交换时，相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。