Java入门第34课——冒泡排序算法

迷南。 2022-01-30 14:27 135阅读 0赞

## 问题 ##

冒泡排序(Bubble Sort)，是一种比较简单的排序算法。在冒泡排序算法中，需要重复的走访要排序的数列，一次比较两个元素，如果它们的大小顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换的元素，也就是说该数列已经排序完成。由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序。

本案例要求使用冒泡排序算法实现对数组的排序。有一个长度为10的整型数组，使用冒泡排序算法将数组按照升序排列，并输出排序的过程以及结果。程序交互情况如图所示：

![image.png][]

## 方案 ##

为了理解冒泡排序算法，我们先假设有一个长度为7的数组，数组内容如图所示：

![image.png][image.png 1]

上图中的数组元素为无序状态，为实现升序排列，可以先进行第一轮比较，过程大致如下：

1.先比较第一对相邻的元素(第一个位置的89和第二个位置的50):如果第一个比第二个大，就交换两个数值；

2.继续比较第二对相邻的元素(第二个位置和第三个位置):如果第二个位置上的数值大于第三个位置上的数值，则交换；

3.继续下去，重复上述的比较工作，直到结尾的最后一对；此时，一轮比较交换完成后，最后的元素则是数列中最大的数。

第一轮比较的过程如图所示：

![image.png][image.png 2]

由上图可以看出，第一轮比较后，已经将数组中的最大值通过位置交换，移动到数组的最后位置上。但是，其余的元素依然为无序状态，因此，依然进行第二轮比较：针对除最后一个元素外的其他元素重复以上步骤，以找到剩余元素中的最大数，且放置到倒数第二的位置上。第二轮比较的过程如图所示：

![image.png][image.png 3]

由上图可以看出，第一个位置上的50比第二个位置上的84小，因此不发生交换；而其他位置将依次发生变换，从而将84交换到倒数第二的位置上。

然后，继续进行其他轮比较，持续进行，每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较，则排序完成。整个排序的过程如图所示：

![图111.jpg][111.jpg]

由上图可以看出，实现冒泡排序算法时，需要使用嵌套的两个循环来实现：外层循环用于控制排序的轮次，里层循环用于控制每轮排序中的两两交互。

## 步骤 ##

实现此案例需要按照如下步骤进行。

## 步骤一：定义类及main方法 ##

首先定义一个名为BubbleSort的类，并在类中添加Java应用程序的主方法main，代码如下所示：

public class BubbleSort{
            public static void main(String[] args){
            }
        }

## 步骤二：创建数组 ##

在main方法中创建一个长度为10的数组，并使用for语句构建一个10次的循环，在每次循环中，随机产生一个0到99之间的整数，并存入数组，然后，打印数组的内容显示在界面上。

此案例中，使用Random类的nextInt()方法产生随机数。代码如下所示：

import java.util.Random;
        import java.util.Arrays;
        
        public class BubbleSort{
            public static void main(String[] args){
                
                //创建数组
                int[] arr=new int[10];
                Random ran=new Random();
                for(int i=0;i<arr.length;i++){
                    arr[i]=ran.nextInt(100);
                }
                System.out.println(Arrays.toString(arr));
            }
        }

注意：此步骤中，需要导入java.util包下的Random类和Arrays类。

## 步骤三：排序 ##

使用冒泡排序算法对数组进行排序：每一轮比较中，两两相比，找到更大的数值移动到最后，直到都比较过一遍。为便于查看排序的过程，将每轮比较后的数组内容输出显示，并将最后的结果输出到控制台。代码如下所示：

## 关注公众号，获取学习视频 ##

### ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdWp1bmthbmczNjM_size_16_color_FFFFFF_t_70][] ###

[image.png]: /images/20220130/554c9948c0ab46ceb55ba42d117e942c.png
[image.png 1]: /images/20220130/ddbd70a92dcd442bbd40dede07aad5c5.png
[image.png 2]: /images/20220130/3e709f5414c44e8caa3a76f9d217d75e.png
[image.png 3]: /images/20220130/6abfa114734e46078a08037e6b83cff7.png
[111.jpg]: /images/20220130/adc90b02c7b64d9fb75fb1175607cd7b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdWp1bmthbmczNjM_size_16_color_FFFFFF_t_70]: /images/20220130/4d69f276cf9c40a2987462bd2bdd6694.png