小白算法_(1)

前言

笔者属于算法小白一枚，本系列文章属于算法的学习笔记，也希望能给算法小小白起到些许的指引作用。如果有算法大佬不小心点了进来，只能说一声抱歉打扰了。

正文

题目

请实现一个冒泡排序，升序排列。

原理

1. 比较相邻的元素，如果前面一个比后面一个大，就交换他们两个。
2. 对每一对相邻元素作同样的工作，从开始的一对到结尾的最后一对。这步做完以后，最大元素就在队列尾部。
3. 重复以上步骤，找出第二大、第三大的元素等等依次排列在尾部，直到没有任何一对数字需要比较。

实现

冒泡排序需要两层循环才能实现，个人建议先梳理清楚一层循环做了什么事情，得到了什么结果，最后再加上一层循环嵌套，思路会更清晰一些。

假设待排序的数组：[6, 4, 2, 1, 8, 3, 7, 9, 5]

我们在一层循环里面想要将最大的元素放在队列尾部，结合算法原理，不难写出以下代码：

public static void main(String[] args) {
    int[] array = {6, 4, 2, 1, 8, 3, 7, 9, 5};
    for (int j = 0; j < array.length - 1; j++) {
        if (array[j] > array[j + 1]) {
            int tmp = array[j];
            array[j] = array[j + 1];
            array[j + 1] = tmp;
        }
    }
    System.out.println(Arrays.toString(array));
}

得到数组：[4, 2, 1, 6, 3, 7, 8, 5, 9]

分析：

1. 数组一共9个元素，现在找到了最大的元素，并且这个元素在队列尾部。
2. 接下来我只需要在剩下的8个元素里面找到第二大的元素就好了。

继续写代码：

public static void main(String[] args) {
    int[] array = {6, 4, 2, 1, 8, 3, 7, 9, 5};
    for (int j = 0; j < array.length - 1; j++) {
        if (array[j] > array[j + 1]) {
            int tmp = array[j];
            array[j] = array[j + 1];
            array[j + 1] = tmp;
        }
    }
    for (int j = 0; j < array.length - 2; j++) {
        if (array[j] > array[j + 1]) {
            int tmp = array[j];
            array[j] = array[j + 1];
            array[j + 1] = tmp;
        }
    }
    System.out.println(Arrays.toString(array));
}

得到数组：[2, 1, 4, 3, 6, 7, 5, 8, 9]

分析：

1. 仔细观察两段 for 循环代码，不难发现唯一的区别就是array.length - 1 和 array.length - 2。
2. 容易想到，当我们想要在剩余的7个元素里面找到第三大的元素的时候，对应的就是array.length - 3。抽象出来就是array.length - i。
3. 那么我们最终需要减到哪个数字为止呢？很简单，对9个元素排序，只需要进行8次即可。
4. 就这样，新的一层循环嵌套已经呼之欲出了。int i = 1; i < array.length; i++。

改进代码：

public static void main(String[] args) {
    int[] array = {6, 4, 2, 1, 8, 3, 7, 9, 5};
    for (int i = 1; i < array.length; i++) {
        for (int j = 0; j < array.length - i; j++) {
            if (array[j] > array[j + 1]) {
                int tmp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = tmp;
            }
        }
    }
    System.out.println(Arrays.toString(array));
}

到这里，一个完整的冒泡排序就实现了。

实际上，这并不是最完美的实现，因为如果待排序的数组内部已经有序，比如[1, 2, 3, 4, 5, 6, 7, 8, 9]，以上代码还是会老老实实的依次比对，尽管它不会交换数据。因此，我们可以增加一个标记位用于判断一次比对过程当中是否交换了数据，如果没有，则代表数组已经有序，直接退出循环即可。

最终代码：

public static void main(String[] args) {
    int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    for (int i = 1; i < array.length; i++) {
        boolean exchange = false;
        for (int j = 0; j < array.length - i; j++) {
            if (array[j] > array[j + 1]) {
                int tmp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = tmp;
                exchange = true;
            }
        }
        if (!exchange) {
            break;
        }
    }
    System.out.println(Arrays.toString(array));
}

总结

冒泡排序是一个非常简单的入门级排序，它具有如下特点：

1. 时间复杂度是O(n²)。
2. 空间复杂度是O(1)。
3. 是一个稳定排序。

请深入理解了它的实现以后，在纯文本编辑的环境下手撕了它。