Java / 冒泡排序

冒泡排序

1. 前言

本节内容是排序算法系列之一:冒泡排序,主要讲解了冒泡排序的主体思路,选取了一个待排序的数字列表对冒泡排序算法进行了演示,给出了冒泡排序算法的 Java 代码实现,帮助大家可以更好地理解冒泡排序算法。

2. 什么是冒泡排序?

冒泡排序(Bubble Sort),是计算机科学与技术领域中较为简单的一种排序算法。

它重复地遍历要排序的序列,会依次比较两个相邻的元素,如果发现两个相邻的元素顺序错误就把它们交换过来。遍历序列的工作会重复地进行直到没有相邻的元素需要交换位置,也就是说序列的排序工作已经完成。

冒泡排序的算法名称的由来就是因为在排序的过程中,按照排序规则(升序或者降序),越小或者越大的元素会经过交换之后慢慢 “浮” 到序列的顶端,就如同水中的气泡一样最终会浮到顶端一样,所以起名为 “冒泡排序”。

3. 冒泡排序过程

在介绍完冒泡排序之后,我们一起来看一下冒泡排序的实现步骤具体是什么样的吧。这里我们假设待排序的序列为 [9,2,11,7,12,5],我们按照从小到大的序列进行排序。

3.1 算法步骤

  1. 步骤 1:

比较待排序序列中相邻的两个元素,如果发现左边的元素比右边的元素大,则交换这两个元素;

  1. 步骤 2:

每一对相邻的两个元素重复步骤 1 的动作,从左至右依次执行;

  1. 步骤 3:

针对待排序序列中除了最右边的一个元素之外,重复步骤 1 步骤 2 的工作;

  1. 步骤 4:

持续以上步骤 1 步骤 2 步骤 3 的工作,每重复一次需要排序的序列中少一个最右边的元素,直到没有任何一对数字需要比较排序。

其实,上面的步骤 2 每执行一次,都有一个排序好的数字放到需要排序的序列的最右边,这样一直重复,可以完成最开始的整个待排序序列的排序工作。接下来,让我们用上面的待排序数字队列 [9,2,11,7,12,5] 进行整个算法步骤的排序演示工作。

3.2 算法演示

按照排序步骤,首先我们会比较待排序序列中(9,2)这一对需要排序的序列,按照从小到大进行排序,需要交换位置,形成序列(2,9),如下:
图片描述

接着,我们调用步骤 2,重复每一对的排序工作,整个过程如下:
图片描述

步骤 2 会依次比较待排序序列中相邻的两个元素,按照如上过程一样。当相邻的两个元素已经是排序好的时候,无需交换顺序,否则交换相邻两个元素的顺序。

Tips: 步骤 2 每执行一次都会有一个元素排序好,就是所谓的冒泡的过程,按照从小到大的顺序排列时,每次都会有一个最大的元素排序好,放在待排序序列的最右边。

完成步骤 2 之后,说明我们已经把最大的一个元素 12 排序好啦,接下来我们只需要对序列 [2,9,7,11,5] 进行排序即可,就如 步骤 3 描述一下,然后重复 步骤 1 步骤 2 中的工作,具体过程执行如下:
图片描述
我们发现当我们执行 步骤 3 之后,之前的待排序队列 [2,9,7,11,5] 中的最大的一个元素 11 又已经排序好啦,接下来我们只需要调用 步骤 4 的工作,重复之前 步骤 1 步骤 2 步骤 3,这里我们就不在演示,只是重复性的进行排序工作,每执行一次 步骤 4,就已经把一个元素排序好,待排序的序列中就减少了一个序列,每次会有一个排序好的数字和一个剩下的待排序数列。其实,整个过程如下:
图片描述
从上面的示例可以看出,其实整个冒泡排序的过程,每次都会把最大的一个数字排序出来,放在整个序列的最右边,重复执行整个过程,直到整个序列中已经没有需要排序的数值了。

4. Java 代码实现

在说明冒泡排序的整个过程之后,接下来,我们看看如何用 Java 代码实现冒泡排序算法。

import java.util.Arrays;

public class BubbleSort {

    public static void main(String[] args) {
        
        //初始化需要排序的数组
        int array[] = {9,2,11,7,12,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 temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
        }
        //打印出排序好的序列
        System.out.println(Arrays.toString(array));
    }

}

运行结果如下:

[2, 5, 7, 9, 11, 12]

代码中的第 8 行初始化一个需要排序的数组,后面按照从小到大的排序规则,实现了数组的排序。第 11 行是外层循环,不断地重复排序工作。第 14 行是内层循环,不断地实现每一次 “冒泡” ,将最大的一个元素找出。第 17 至第 21 行实现当相邻两个元素需要交换时,交换相邻的两个元素的功能。第 25 行打印出排序好的数组。

5. 小结

本节主要学习了冒泡排序算法,在学完本节课程之后,需要熟悉冒泡排序的算法流程,知道冒泡排序算法的实现思路,可以自己用代码实现冒泡排序算法。