数据结构之排序：冒泡排序

冒泡排序（Bubble Sort）

基本思想

将待排序的数组看成从上到下排放，把关键字值较小的记录看成“较轻的”气泡，关键字值较大的看成“较重的”石块，较轻的上浮，较重的下沉。所有的气泡和石块都在相应的位置，则排序结束。

主要步骤

1. 置初值i=1
2. 在无序序列{r[0], r[1], … , r[n-i]}中，从头到尾依次比较相邻的两个记录r[j]与r[j+1]，注意0<=j<=n-i-1，如果r[j]>r[j+1]，则交换位置
3. i=i+1
4. 重复2-3，直到步骤2中未发生记录交换或者i=n-1为止

java实现代码：

/**
 * 冒泡排序1 O(n2)
 * 重量大的下沉，重量小的上浮
 * @param arr
 */
public static <T extends Comparable<T>> void bubbleSort1(T[] arr) {
// 第i轮排序是否发生了互换，如果不再发生互换，则排序完成
boolean isSwapHappened = true;
for (int i = 1; i < arr.length && isSwapHappened; i++) {
            isSwapHappened = false;
for (int j = 0; j < arr.length - i; j++) {
if (arr[j].compareTo(arr[j + 1]) > 0) {   //逆序正序修改符号即可
                    swap(arr, j, j + 1);
                    isSwapHappened = true;
                }
            }
        }
    }

/**
 * 交换
 * @param t1
 * @param t2
 */
public static <T extends Comparable<T>> void swap(T[] arr, int i, int j) {
        T tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

参考：
1. 刘小晶，数据结构——Java语言描述（第2版），清华大学出版社
2. MARK A W， 数据结构与算法分析: Java 语言描述，机械工业出版社