排序算法（一） 冒泡排序法

冒泡排序法可谓是我们学到的第一个排序算法了，以其简单易懂而闻名，但是这个算法又是特别的垃圾，因为效率及其的低下。

下面是一些经典的排序算法的时间复杂度：

排序算法的时间复杂度

别看这个冒泡排序法的时间复杂度和选择，插入是一样的，但是效率却远远比选择，插入低，尤其是数据量很大的时候。

冒泡排序的思路

冒泡排序的思路就是每次把最大的数挑出来放到数组的最后面(排序皆是从小到大)。如下图所示

冒泡排序

冒泡排序动图

每一次将最大的元素移动到数组的后面，移动了5次，这个数组就是从大到小有序的了。

代码的实现

冒泡排序比较容易理解，代码也是比较好写的。

public static void bubbleSort(int[] arr) {
        boolean flag = false;
        int temp;

        for (int i = 0; i < arr.length-1; i++) {
            for (int j = 0; j < arr.length-i-1; j++) {
                if (arr[j] > arr[j+1]) {
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    flag = true;
                }
            }
            if (!flag) {
                break;
            }else {
                flag = false;
            }
        }
    }

代码的几点说明：

  1. i和j的含义

    • 可以清除的看到在两个for循环的循环体中是没有i变量的，也就是说i变量只是用来计量有几个大数被移动到了数组的末尾。
    • j变量是用于交换. j < arr.length - 1-i的作用是后面的几个变量已经排过序了，他们就是最大的那几个数，j变量可以不用对他们进行比较交换啦。j从0开始每次和j+1进行比较，如果arr[j]大，也就是前面的数大，就把他往后面移动。如此一来，前面的几个数中最大的那个数就被移动到当前j所比较的末尾arr.lenght-1-i处。

  2. flag的作用是什么？

    flag这个是对冒泡排序法的一个优化，虽然优化过后这个算法还是一样的垃圾。。。flag所代表的含义是该次循环中有没有发生过交换。一开始我们将其置为flag(不初始化也是可以的，boolean型的变量的初始值就是false).当本次循环进行过交换的时候，将flag置为true。然后再将循环置为false。当有某次的循环中没有进行过交换，这个也就是意味着此时数组前面的那几个数已经是有序的了，而数组后面的数同样也是有序的，所以退出循环排序结束。

冒泡排序的测试：

测试环境及工具：我的电脑 Huawei MateBook 13+JDK1.8+Eclipse

测试手段：随机生成80000个[0,800000）的整数的数组进行排序，观察所花费的时间

测试代码：

public static void main(String[] args) {
        int[] arr = new int[80000];
        for (int i = 0; i < arr.length; i++) {
//            arr[i] = (int) (Math.random()*800000);
            arr[i] = new Random().nextInt(800000);
        }
//        System.out.println(Arrays.toString(arr));
        long start_time = System.currentTimeMillis();
        bubbleSort(arr);
        long end_time = System.currentTimeMillis();
//        System.out.println(Arrays.toString(arr));
        System.out.println("Time :"+(end_time-start_time)+"ms");

测试结果：

  1. Time： 8786ms
  2. Time： 8706ms
  3. Time： 8661ms

总结

哇！！！八万个数据的排序才花了八秒，这个算法好厉害啊！！！我是不会告诉你后面的堆排序，归并排序排序八万个数只是用了10ms，排序八百万个也用不了一秒的。。

冒泡排序算法中有着大量的数据的交换，这就注定了这是一个低效的算法。但是还好的是，冒泡排序算法是一个稳定的算法。所谓稳定的算法就是拥有相同的值的数据在排序完之后的顺序保持不变.

比如说 8 3 4 5 3 6 排序后是 3 3 4 5 6 8，排序完的第一3仍然是原来数组中的第一个3

赏

一枚小菜鸡