冒泡排序

冒泡排序

写在前面：这里将气泡大（值较大）的上移。

import java.util.Arrays;

/**
 * 冒泡排序.算法描述：
 * 初始，a[0...n-1]为无序区，“垂直排列”；
 * 第一趟扫描，从无序区底部向上，两两比较相邻气泡，大气泡（较大值）上移；第一趟扫描结束，最大的气泡移到顶部（即有序区）；
 * 重复扫描无序区a[0...n-2]；
 * 总共进行n-1趟扫描得到有序区，或者若一趟扫描中未发生气泡位置的交换，说明已全部有序。
 * O(T) = n*(n+1)/2
 * @author yi
 * @date 2015年7月3日
 *
 * @me 1. while 很好用啊 while(len-1>0 && unSequenced) 2.跳出循环的条件 3.标志位的名字问题 4.方法外提，减少主函数体
 */
public class BubbleSort {
    /**
     * 冒泡排序
     * 
     * @param arr
     */
    public static void bubblesort(int[] arr) {
        int len = arr.length;
        // 标志一次循环中是否进行了交换
        boolean unSequenced = true;
        // 每次循环都将最大值移到数组尾，下一次循环的元素数减1
        // 若上一次循环未交换任何元素，说明已有序
        while(len-1>0 && unSequenced) {
            unSequenced = false;
            // 两两比较相邻元素，较大值后移
            for(int j = 0; j < len-1; j++) {
                if(arr[j] > arr[j+1]) {
                    swap(arr, j, j+1);
                    unSequenced = true;
                }
            }
            len--;
            // 每次循环后打印排序结果
            System.out.println(Arrays.toString(arr));
        }
    }
    
    /**
     * 交换数组元素
     * 
     * @param arr
     * @param i
     * @param j
     */
    static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    
    /**
     * 主函数，定义测试数据，调用冒泡排序方法
     * 
     * @param argus
     */
    public static void main(String[] argus) {
        // 测试例子
//        int[] arr = {6, 2, 4, 1, 5, 9};           // 显示引入标志位后的优化效果
        int[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1};  // 显示冒泡排序：每次将最大值移到最后
        System.out.println(Arrays.toString(arr));
        BubbleSort.bubblesort(arr);
    }
}

参考资料（这里也有演示动画）：

http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.3.1.1.htm