阅读:0       作者:严长生

冒泡排序算法原理及实现(超详细)

冒泡排序(Bubble Sort)是排序算法里面比较简单的一个排序。它重复地走访要排序的数列,一次比较两个数据元素,如果顺序不对则进行交换,并一直重复这样的走访操作,直到没有要交换的数据元素为止。

冒泡排序的原理

为了更深入地理解冒泡排序的操作步骤,我们现在看一下冒泡排序的原理。

首先我们肯定有一个数组,里面存放着待排序的元素列表,我们如果需要把比较大的元素排在前面,把小的元素排在后面,那么需要从尾到头开始下面的比较操作:
  1. 从尾部开始比较相邻的两个元素,如果尾部的元素比前面的大,就交换两个元素的位置。
  2. 往前对每个相邻的元素都做这样的比较、交换操作,这样到数组头部时,第 1 个元素会成为最大的元素。
  3. 重新从尾部开始第 1、2 步的操作,除了在这之前头部已经排好的元素。
  4. 继续对越来越少的数据进行比较、交换操作,直到没有可比较的数据为止,排序完成。

注意,看完了这里的操作步骤,我们可以想一下,如果从头到尾进行操作是否可以?当然不可以,不过这样可以完成从小到大的排序。

假如我们要把 12、35、99、18、76 这 5 个数从大到小进行排序,那么数越大,越需要把它放在前面。冒泡排序的思想就是在每次遍历一遍未排序的数列之后,将一个数据元素浮上去(也就是排好了一个数据)。

我们从后开始遍历,首先比较 18 和 76,发现 76 比 18 大,就把两个数交换顺序,得到 12、35、99、76、18;接着比较 76 和 99,发现 76 比 99 小,所以不用交换顺序;接着比较 99 和 35,发现 99 比 35 大,交换顺序;接着比较 99 和 12,发现 99 比 12 大,交换顺序。最终第 1 趟排序的结果变成了 99、12、35、76、18,排序的过程如图 1 所示。


图 1 第 1 趟冒泡排序的过程示例

经过第 1 趟排序,我们已经找到了最大的元素,接下来的第 2 趟排序就只对剩下的 4 个元素排序。第 2 趟排序的过程示例如图 2 所示。


图 2 第 2 趟冒泡排序的过程示例

经过第 2 趟排序,结果为 99、76、12、35、18。接下来应该进行第 3 趟排序了,剩下的元素不多,比较次数也在减少。

第3趟排序的结果应该是 99、76、35、12、18,接下来第 4 趟排序的结果是 99、76、35、18、12,经过 4 趟排序之后,只剩一个 12 需要排序了,这时已经没有可比较的元素了,所以排序完成。

这个算法让我想起了小时候在操场排队跑步,老师总是说:“高的站前面,低的站后面”。我们一开始并不一定会站到准确的位置上,接着老师又说:“你比前面的高,和前面的换换,还高,再和前面换换”,就这样找到了自己的位置。

通过这个例子,你是否已经完全掌握了排序算法的精髓呢?

冒泡排序的实现

通过对冒泡排序原理的学习,我们应该能够很容易地写出实现代码了。首先我们需要从后往前遍历待排序数组,然后重复这个步骤,继续遍历剩下的待排序的数列,这样我们就需要一个双重循环去完成这个算法。
public class BubbleSort {
    private int[] array;
   
    public BubbleSort(int[] array) {
        this.array = array;
    }

    /**
     * 从小到大
     */
    public void sort() {
        int length = array.length;
        if (length > 0) {
            for (int i = 1; i < length; i++) {
                for (int j = 0; j < length - i; j++) {
                    if (array[j] > array[j + 1]) {
                        int temp = array[j];
                        array[j] = array[j + 1];
                        array[j + 1] = temp;
                    }
                }
            }
        }
    }
   
    /**
     * 从大到小
     */
    public void sort2() {
        int length = array.length;
        if (length > 0) {
            for (int i = length - 1; i > 0; i--) {
                for (int j = length - 1; j > length - 1 - i ; j--) {
                    if (array[j] > array[j - 1]) {
                        int temp = array[j];
                        array[j] = array[j - 1];
                        array[j - 1] = temp;
                    }
                }
            }
        }
    }
   
    public void print() {
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
    }

}
下面是冒泡排序的测试代码。
public class SortTest {
    public static void main(String[] args) {

        testBubbleSort();
    }
   
    /**
     * 冒泡排序
     */
    private static void testBubbleSort() {
        int[] array = {5, 9, 1, 9, 5, 3, 7, 6, 1};
        BubbleSort bubbleSort = new BubbleSort(array);
        bubbleSort.sort2();
        bubbleSort.print();
    }
}

冒泡排序的特点及性能

通过冒泡排序的算法思想,我们发现冒泡排序算法在每轮排序中会使一个元素排到一端,也就是最终需要 n-1 轮这样的排序(n 为待排序的数列的长度),而在每轮排序中都需要对相邻的两个元素进行比较,在最坏的情况下,每次比较之后都需要交换位置,所以这里的时间复杂度是 O(n2)。其实冒泡排序在最好的情况下,时间复杂度可以达到 O(n),这当然是在待排序的数列有序的情况下。在待排序的数列本身就是我们想要的排序结果时,时间复杂度的确是 O(n),因为只需要一轮排序并且不用交换。但是实际上这种情况很少,所以冒泡排序的平均时间复杂度是 O(n2)

对于空间复杂度来说,冒泡排序用到的额外的存储空间只有一个,那就是用于交换位置的临时变量,其他所有操作都是在原有待排序列上处理的,所以空间复杂度为 O(1)

冒泡排序是稳定的,因为在比较过程中,只有后一个元素比前面的元素大时才会对它们交换位置并向上冒出,对于同样大小的元素,是不需要交换位置的,所以对于同样大小的元素来说,相对位置是不会改变的。

冒泡排序算法的时间复杂度其实比较高。从 1956 年开始就有人研究冒泡排序算法,后续也有很多人对这个算法进行改进,但结果都很一般,正如 1974 年的图灵奖获得者所说的:“冒泡排序除了它迷人的名字和引起的某些有趣的理论问题,似乎没有什么值得推荐的。”

冒泡排序的适用场景

对于冒泡排序,我们应该对它的思想进行理解,作为排序算法学习的引导,让我们的思维更加开阔。

虽然冒泡排序在我们的实际工作中并不会用到,其他排序算法多多少少比冒泡排序算法的性能更高,但是我们还是要掌握冒泡排序的思想及实现,并且在面试时还是有可能会用到。