冒泡排序法

• 对于大小为n的数组a，用i遍历元素(遍历范围[0, n-2])，每次拿a[i]和a[i+1]比较，假如a[i]>a[i+1]，两者交换。
• 最多重复上述操作n-1次。

• 为什么不是重复n次？
  因为当完成第m次冒泡时(m>=0 && m<=n)，a[n-1-m, n-1]是有序的。即执行完第n-1次操作后，a[0, n-1]已经有序，因此不用执行第n次冒泡。
• 最多是什么意思？
  考虑一种极端情况，当数组本身已经是有序的，执行完第一次冒泡操作，并没有元素发生交换。意思是说，假如冒泡排序没有发生元素的交换，数组就是有序的。判断数组是否有元素交换，可以提前中止冒泡操作。

• 是否是稳定排序算法
  是的。
• 是否是原地排序算法？
  是的。
• 空间复杂度
  因为时候原地排序算法，所以是O(1)。
• 时间复杂度
  • 最优时间复杂度
    假设数组本身有序，执行一次就行了，复杂度是O(n)。
  • 最差时间复杂度
    需要执行n-1次冒泡操作就是最坏的情况。

    设m是冒泡次序，则有
    t(m) = n - m, t为每次冒泡的时间消耗
    T(n) = t(1) + t(2) + ... + t(m)
        = n - 1 + n - 2 + ... + n - m
        = n*m - (1+m)*m/2
    当m = 1时，T(n) = n - 1，即O(n)
    当m = n - 1时，T(n) = n(n-1)/2， 即O(n2)
    

public void sort() {
    // data是要排序的数组
    if (data == null) {
        setDataRandomly(); // 设置随机数组
    }
    for (int i = 0; i < getSize()-1; i++) {
        for (int j = 0; j < getSize() - 1 - i; j++) {
            if (data[j] > data[j+1]) {
                int temp = data[j];
                data[j] = data[j+1];
                data[j+1] = temp;
            }
        }
    }
}