冒泡排序

原文链接： 冒泡排序

冒泡排序

动画效果

冒泡排序是一种交换排序，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，知道没有反序的记录为止。冒泡的实现上有很多种变化，我们主要介绍3中。

1、最简单的冒泡排序

/**
 * Created by liuqiang on 16/4/8.
 * 冒泡排序
 */
public class BubbleSort {
    public static void main(String[] args) {
        int arr[] = {9, 1, 5, 8, 3, 7, 4, 6, 2};
        print(arr);
        sort(arr);
        print(arr);
    }
    /**
     * @param args 待排序的数组
     * 思路：让每一个关键字都和他后面的每一个关键字比较，
     * 如果大则交换，这样第一个位置的关键字就在一次循环
     * 之后变成了最小值
     */
    public static void sort(int[] args) {
        for (int i = 0; i < args.length; i++) {
            for (int j = i + 1; j < args.length; j++) {
                if (args[i] > args[j]) {
                    swap(args, i, j);    //交换数组中的两个元素的位置
                }
            }
        }
    }
    /**
     * 交换数组args 中的下标为 i 和 j 的元素
     *
     * @param args
     * @param i
     * @param j
     */
    public static void swap(int[] args, int i, int j) {
        int temp = args[i];
        args[i] = args[j];
        args[j] = temp;
    }
    /**
     * 数组打印辅助方法
     *
     * @param args
     */
    public static void print(int[] args) {
        System.out.print("数组的值: [");
        for (int m : args) {
            System.out.print(m + ",");
        }
        System.out.println("]");
    }
}

其实以上代码严格意义上来说不算是冒泡排序算法，因为他不满足“两两比较相邻记录”的冒泡思想。它应该算是最简单的交换排序而已。
2、真正的冒泡

/**
     * 真正的冒泡排序算法
     *
     * @param args 待排序的数组
     * 
     */
    public static void sort2(int[] args) {
        for (int i = 0; i < args.length; i++) {
            for (int j = args.length - 2; j >= i; j--) {    //从后往前循环
                if (args[j] > args[j + 1]) {
                    swap(args, j, j + 1);
                }
            }
        }
    }

或者

public static void sort3(int[] args) {
       for (int i = 0; i < args.length; i++) {    //趟数
           for (int j = 0; j < args.length - 1 - i; j++) {  //比较次数
               if (args[j] > args[j + 1]) {
                   swap(args, j, j + 1);
               }
           }
       }
   }

3、冒泡排序的优化

我们来看这个序列的排序{2,1,3,4,5,6,7,8,9}如果用上面的排序算法，当i=0的时候交换一次之后，这个序列已经有序，但是程序依然会从i=0 遍历到i=args.length 。所以当i=1的时候没有进行任何的数据交换，就说明这个序列有序了，可以不用进行后面的循环操作了。为了实现这个想法，我没可以设置一个标志位，flag来控制循环的结束。

/**
    * 冒泡排序的优化
    *
    * @param args
    */
   public static void sort4(int[] args) {
       boolean flag = true;    //用flag来做标记为，用来标识当前序列是否发生了数据交换
       for (int i = 0; i < args.length && flag; i++) {
           flag = false;
           for (int j = args.length - 2; j >= i; j--) {    //从后往前循环
               if (args[j] > args[j + 1]) {
                   swap(args, j, j + 1);
                   flag = true;    //发生了数据交换设置为true
               }
           }
       }
   }