Java数据结构与算法(4) -冒泡排序

前言

最近编程状态很自由，我挺喜欢这种感觉。不过还是要给自己制定一个计划，每天学习一小节《Java数据结构与算法》和看一小节刘宇波老师的《数据结构与算法》视频，还有就是学习Spring Boot项目课程。然后每天晚上的时候，写一篇简书总结自己一天回顾的知识。

---

从简单的冒泡排序开始

冒泡排序算法运行起来十分慢，但在概念上它是排序算法中最简单的，因此冒泡排序算法在开始研究排序技术时是一个非常好的算法。

---

什么是冒泡排序?

对几个无序的数字进行排序，最常用的方法是所谓的冒泡排序。算法思想是每次比较2个相邻的数字，将小的放在前面，将较大的放在后面，这样就可以将这些数中最大的找出来放在到最后。然后再比较剩下的数字，再在这些数字中找出最大的，直到所有的数字按照从小到大的顺序进行排序。

提炼思想

• 在算法执行的时候，最大的数据项总是冒泡到数据的顶端。

• 假如有N个数字需要进行排序，在对所有的数字进行了第一趟排序之后，进行了N - 1次比较，并且按照数字之间的初始位置，进行了最少0次，最多N - 1次交换，数组最末端的数据项就此排定。

• 我们进行第二趟排序的时候，再一次地从左到右，两两比较，并且在适当的时候交换数字之间的顺序，这一次只需要比较到右边第二个数字(位置 N - 2)就行了，因为最大的数字已经到了最后位置，既N - 1号位置。

开始练手

• 只有把思路理清楚了，才能开始写代码。

public class BubbleSortDemo {
    public static int[] a = { 2, 4, 6, 8, 3, 6, 9, 12 };

    public static void main(String[] args) {
        sort();
        display();
    }

    public static void sort() {
        int count = a.length;

        for (int i = 0; i < count - 1; i++) {
            for (int k = 0; k < count - 1 - i; k++) {
                if (a[k] > a[k + 1]) {
                    swap(k, k + 1);
                }
            }
        }
    }

    public static void swap(int x, int y) {
        int temp = a[x];
        a[x] = a[y];
        a[y] = temp;
    }

    public static void display() {
        int count = a.length;

        for (int i = 0; i < count; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println("");
    }
}

• 运行程序，看控制台输出结果。

image.png

---

性能优化

我们使用的是一个独立的swap()方法来执行交换操作的。它只是交换数组中的两个数据项的值，使用一个临时变量来存储第一个数据项的值，然后把第二项的值赋给第一项，之后再让第二项的值等于临时变量。实际上，使用一个独立的swap()方法不一定好，因为方法调用会增加一些额外的开销，如果写自己使用的排序程序，最好将交换操作这段代码直接放到程序中，这样可以提高一些速度。

---

冒泡排序的效率

• 我们发现在第一趟排序时进行了9次比较，第二趟排序时进行了8次比较，以此类推，直到最后一趟进行了一次比较。那么10个数据项，一共就进行了9 + 8 + ... + 1 = 45次，也就是N * （N - 1）/ 2。如果初始数据项时逆序的时候，我们每次比较都需要交换。可以知道冒泡排序运行需要O(N^2)时间级别，这样速度是很慢的。

• 只要看到了一个循环嵌套在另一个循环中，就可以怀疑这个算法的运行时间为O（N^2）级。

---

尾言

勿以善小而不为。