排序算法中的冒泡和选择排序详解（持续更新系列）

悠悠 2024-03-16 13:24 40阅读 0赞

**本系列文章为Java基础入门内容，致力于为大家详细讲解学习Java中的一些难点、常见点等，内容由浅入深。**

**文末有全文重点总结及配套视频资料，更多相关技术问题欢迎和我们一起交流讨论！[更多学习资料可点这里获取][Link 1]**

## 前言 ##

我们要想成为一个优秀的程序员，其实非常关键的一点就是要锻炼培养自己的编程思维，就好比一个狙击手，要通过大量的射击训练要用大量的子弹喂出来。

**同样的，一个优秀的程序员，他的逻辑和编程思维，也是靠大量的训练锻炼出来的，而这个训练经常是通过各种“算法”来实现的。** 所以作为一个从零开始学习的小白，我们必然要学习各种编程算法。这些算法，一方面可以锻炼我们的编程思维，另一方面也是为了完成工作，很多项目中都会或多或少的用到一些算法，**并且程序员面试时，算法也是必考的一项。** 基于这些因素，接下来会给大家介绍一些经典的算法，比如**排序、查找算法，当然还会给大家介绍一些经典的数据结构，比如二叉树、红黑树、图等，那么就请各位认真学习吧。**

--------------------

全文大约【**4400】** 字，不说废话，只讲可以让你学到技术、明白原理的纯干货！本文带有丰富的案例及配图视频，让你更好地理解和运用文中的技术概念，并可以给你带来具有足够启迪的思考…

## 一. 排序算法 ##

### 1. 概念 ###

所谓排序，就是使一串记录可以按照其中某个或某些关键字的大小，根据递增或递减的排列起来。而排序算法，就是使得数据按照特定要求排列的方法。我们在开发时常用的排序算法有如下几个：

*  **直接插入排序**
 *  **希尔排序**
 *  **简单选择排序**
 *  **堆排序**
 *  **冒泡排序**
 *  **快速排序**
 *  **归并排序**
 *  **基数排序法**

### 2. 排序算法分类 ###

以上排序算法都属于内部排序，也就是只考虑较小数据量且仅需使用内存的排序算法，他们之间关系如下图所示：  
![在这里插入图片描述][ccbf01739dbb485cb7c18258fbf53fd4.png]

因为实际上具体的排序算法非常多，**这个是Java的系列学习文章，所以我这里不会把每个算法都讲解到。后面我会出一个专门的算法系列文章，敬请大家持续关注哦。**

接下来就以**冒泡、插入、选择、快速、希尔等排序算法为例**，重点给大家讲解一下排序相关的内容。

## 二. 冒泡排序 ##

### 1. 概念 ###

**冒泡排序(Bubble Sort)**，可以说是我们学习编程时必学且知名度最高的一个经典排序算法，同时也是各种考试和面试中出镜率最高的一个排序算法。

首先，我们要知道一点，**冒泡排序属于交换排序算法的一种**。所谓交换排序算法，是指在排序过程中，要发生数组元素的交换。

之所以要把该算法称为“冒泡算法”，这是因为每个大的元素，每次经过交换都会慢慢“浮”到数组的顶端，故名“冒泡排序”。

冒泡排序的核心思想，**是把相邻的元素进行两两比较，当一个元素大于右侧相邻的元素时，就交换它们的位置；当一个元素小于或等于右侧相邻的元素时，则保持位置不变。** 大家注意，冒泡排序只会操作相邻的两个数据。每次冒泡操作都是对相邻的两个元素进行比较，看是否满足大小关系。

### 2. 实现步骤 ###

**接下来我们就以一个数值型的数组为例，向大家介绍冒泡排序的整个排序过程。**

假设，我们现在有一个待排序的数组，其数组元素值依次为\[5，8，6，3，9，,2，1，,7\]。如果我们采用冒泡排序算法，按从小到大的规则对其排序，其详细过程会如下所示：

(1). 将5和8进行比较，因为满足左小右大的规则，不需要交换，保持元素位次不变；

(2). 将8和6进行比较，因不满足左小右大的规则，则需要交换。将8和6位置互换，互换位置后，元素6在下标1这个位置上，元素8在下标2这个位置上；

(3). 接着将8和3进行比较，不满足左小右大规则，需要交换。将8和3位置互换，互换位置后，元素3在下标2的位置上，元素8在下标3的位置上；

(4). 继续将8和9进行比较，满足左小右大规则，不需要交换，保持元素位次不变；

(5). 将9和2进行比较，不满足左小右大的规则，需要交换。将9和2位置互换，互换位置后，元素2在下标4的位置上，元素9在下标5的位置上；

(6). 将9和1进行比较，不满足左小右大的规则，需要交换。将9和1位置互换，互换位置后，元素1在下标5的位置上，元素9在下标6的位置上。

(7). 继续将9和7进行比较，不满足左小右大的规则，需要交换。互换位置后，元素7在下标6的位置上，元素9在下标7的位置上。

如果我们把上述的文字描述，转换为图片，则会如下图所示：

![在这里插入图片描述][5073ec696fda42ecbe196a276c1b665d.png]

这样就完成了第一轮的交换比较。经过第一轮交换后，元素9作为数列中最大的元素，就像是汽水里的气泡一样浮到了最右侧。接着我们继续如此重复上述的比较过程，每一轮结束后，都会有一个本轮最大的元素被移到了最右侧，如下所示：  
![在这里插入图片描述][1f96c57a6846449590857e355e43369f.png]  
每一轮的排序结果最终会如上图所示，所以最终的排序结果就是最后一排的数值结果。

最后我们来总结下，冒泡排序算法的**3个核心步骤：**

*  **第1步：比较相邻的元素**。如果第一个元素比第二个元素大，就将两者交换；
 *  **第2步：对每一对相邻的两个元素进行同样的操作**。从开始第一对到结尾的最后一对，最后的元素就是最大的数。
 *  **第3步：针对所有元素重复以上步骤**。每重复一轮上述步骤，需要操作的元素就会越来越少，直到没有任何一对元素需要比较。

这样我们就理解了冒泡排序的实现思路和过程，接下来我们再来看看该如何在Java中通过代码实现冒泡排序。

### 3. 编码实现 ###

我们根据上述冒泡排序算法的文字描述步骤，利用Java语言进行编程实现，代码如下所示：

public static void bubbleSort(int[] arr) {
        
        int count = 0;
        for (int i = 0; i < arr.length - 1; i++) {
        
            for (int j = 0; j < arr.length - 1-i; j++) {
        
                count++;
                //临时变量 用于交换
                int tmp = 0;
                if (arr[j] > arr[j + 1]) {
        
                    tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                }
            }
        }
    }

最终执行完上述代码后，arr数组就变成了一个有序的数组。

大家要注意，在上述代码中，bubbleSort方法可以接收一个整数类型的数组arr，通过两层for循环，最终就可以实现整型数组元素的冒泡排序。其中：

>  *  内层for循环是将相邻的两个元素进行比较。如果不满足左小右大的规则，就将两个元素进行交换。
>  *  交换相邻的元素时，使用到了临时变量tmp。
>  *  外层for循环，用来控制需要进行几轮比较，即比较的轮次。

### 4. 算法总结 ###

通过上述Java程序，我们就实现了冒泡算法的代码实现，最后**壹哥**再来给大家总结一下冒泡排序算法的时间和空间复杂度等情况。

(1). **冒泡排序的平均时间复杂度是O(n²)** 。如果数组本身已经排好了顺序，在优化后的算法中，需要比较n-1次，此时的时间复杂度是O(n)。而当数组是无序的，在优化后的算法中，需要比较的次数是n(n-1)/2次，此时的时间复杂度是O(n²)。

(2). **冒泡排序的空间复杂度为O(1)** 。

(3). 冒泡排序是原地排序。

(4). 冒泡排序的重点是左右相邻的两个元素进行两两比较，当两个元素数值相同时不换位，所以是稳定排序。

## 三. 选择排序 ##

### 1. 概念 ###

**选择排序(Selection Sort)** 是一种最简单直观的排序算法。即使在我们的日常生活中，大家可能都会经常无意地进行选择排序。比如我们去超市买苹果，你拿了一个袋子，从众多的苹果中挑了一个最大的放入袋中，然后又从剩下的苹果中挑了一个最大的放入袋子。这样如此反复，直到挑够了需要的苹果去结账。这其实就是**选择排序的实现思想，就是不断地从未排序的元素中选择最大(或最小)的元素，放入到已排好序的元素集合中，直到未排序的元素为空。**

基于上述实现思想，我们就可以提取出选择排序的实现原理：

**将一个数组分成有序的区间和无序的区间两部分，初始时有序区间为空，每次从无序区间中选出最小的元素，并放到有序区间的末尾，直到无序区间为空。**

### 2. 实现思路 ###

按照选择排序的实现原理，接下来再把选择排序的实现思路再细化一下：

*  假设，给定一个数组 `int[] arr = {n个数据}`；
 *  第1趟排序，在无序数列 `arr[0] ~ arr[n-1]`中选出最小的数据，将它与arr\[0\]交换；
 *  第2趟，在无序数列 `arr[1] ~ arr[n-1]`中选出最小的数据，将它与arr\[1\]交换；
 *  依此类推，第i趟在无序数列`arr[i]~arr[n-1]`中选出最小的数据，将它与arr\[i\]交换，直到全部排序完成。

但是如何选出最小的一个元素呢？

**我们先任意选一个元素，假设它就是最小的元素(默认为无序区间的第一个元素)，然后让这个元素与无序区间中的每一个元素挨个进行比较。** 如果遇到比自己小的元素，则更新最小值的下标，直到把无序区间遍历完。最后的那个最小值下标对应的数值，就是该无序区间的最小值。

### 3. 实现步骤 ###

同样的，仍然以一个示例来给大家解释选择排序的实现步骤。假如我们现在有一个待排序的数组\[5，8，6，3，9，2，1，7\]，若采用选择排序算法进行排序，其实现步骤如下：

> (1). 初始化待排序数组\[5，8，6，3，9，2，1，7\]；
> 
> (2). 从待排序数组中，选出最小值1，和第一个元素5进行交换，即将最小的元素放在下标0的位置上；
> 
> (3). 在剩下的无序区间的元素中，选择最小的元素2，并将最小的元素2与无序区间的第一个元素8进行交换。交换后，有序区间的元素变为2个，分别是1和2，剩余的为无序区间。
> 
> (4). 依次类推，将所有的元素通过不断选择的方式，按有序的方式放到有序区间，最终把整个数组全部排好顺序。

我们把上述选择排序的文字描述内容，变成对应的图片，会如下图所示：  
![在这里插入图片描述][1072e1ce8b1a49cdb0a85ff6c67b2b81.png]  
![在这里插入图片描述][4b17f5e0da674b95892bebdd63a8052a.png]  
![在这里插入图片描述][cc4e5b0cd7b84c0db7fb03d9a50634c8.png]  
![在这里插入图片描述][20370873ebd342f7927f7a569867dd8f.png]

### 4. 编码实现 ###

接下来也使用Java语言，把选择排序的算法通过编程给大家实现一下：

public static void selectionSort(int[] arr) {
        
        int count = 0;
        //第一个循环用来遍历数组中的所有数字
        for (int i = 0; i < arr.length; i++) {
        
            //初始化一个变量，用来记录最小数字的下标。初始默认假设第一个数字就是最小数字
            int minIndex = i;
            //第二个循环，通过比较获取数组中最小的数字的下标
            for (int j = i + 1; j < arr.length; j++) {
        
                count++;
                //如果找到更小的数字
                if (arr[minIndex] > arr[j]) {
        
                    //将minIndex变量的值修改为新的最小数字的下标
                    minIndex = j;
                }
            }
            //所有数字一个个比较结束之后，就能确认那个数字最小了。
            //将最小的数字替换到第一个位置，将第一个位置的数字放到最小数字原来的位置，就是一次交换。
            arr[i] = arr[i] + arr[minIndex] - (arr[minIndex] = arr[i]);
        }
    }

### 5. 算法总结 ###

选择排序基于最简单的思路，依次把待排序的数据放入到已经排好序的数列中，并继续保持有序。但选择排序的效率较低，时间复杂度是O(n2)。另外随着排序的数据量增长，效率降低的会很快。这里**壹哥**也把选择排序给大家总结一下，核心要点如下：

(1). **选择排序最大的特点，就是不论数列是否有序或乱序，选择排序都要花费一样的时间来计算。** 比如，利用选择排序对数组\[1, 2, 3, 4, 5\]和\[3, 1, 4, 2, 5\]排序，其所需要执行的步骤是一样的。如果用冒泡排序执行已经排好序的数列，则只需要一轮比较就可以得出结果。

(2). **选择排序算法，无论是已排好序或未排序，都需要循环比较n(n-1)/2次**。当n->∞时，无限接近于n²，所以**选择排序算法的时间复杂度为O(n²)** 。

(3). **选择排序算法的空间复杂度是O(1)** 。

(4). **选择排序算法是原地排序算法**，且会发生数据交换操作。

(5). **选择排序是一种简单的排序算法，适用于数据量较小的情况**。根据时间复杂度分析，选择排序所花费的时间会随着数据量增大按照平方倍数增⻓，数据量越大，排序效率就越低。但是选择排序也有优势，即它的实现思维逻辑特别简单，比较容易理解。

--------------------

## 四. 结语 ##

受限于篇幅，今天就先给大家讲一下冒泡和选择排序两种算法，我们总结一下今天的重点：

>  *  **冒泡排序属于交换排序算法的一种；**
>  *  **选择排序算法是原地排序算法的一种；**
>  *  **冒泡排序的核心思想是把相邻的元素进行两两比较，当一个元素大于右侧相邻的元素时，就交换它们的位置；当一个元素小于或等于右侧相邻的元素时，则保持位置不变。**
>  *  **选择排序的实现思想，就是不断地从未排序的元素中选择最大(或最小)的元素，放入到已排好序的元素集合中，直到未排序的元素为空。**

以上就是我们这期的全部内容啦，关于冒泡和选择排序这两种算法，大家有不明白的问题也欢迎在评论区和我们一起交流讨论！

[视频配套资料：戳我  
][Link 2]

[Link 1]: https://work.weixin.qq.com/u/vcad1a71de44a62af1?v=4.0.12.19820
[ccbf01739dbb485cb7c18258fbf53fd4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/ee8859a791544f33aa75b8f3dace81a5.png
[5073ec696fda42ecbe196a276c1b665d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/d753901cb09e483e933dd9309ee45e94.png
[1f96c57a6846449590857e355e43369f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/a62a5840883e42f5b77a14f5f4cfec30.png
[1072e1ce8b1a49cdb0a85ff6c67b2b81.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/c48ef6b1b7ac4d4abd0e16ecb5931c32.png
[4b17f5e0da674b95892bebdd63a8052a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/409d8c13f6e24f279dc52ccf1cd8547b.png
[cc4e5b0cd7b84c0db7fb03d9a50634c8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/f5cae7bb4c754817a094f222255ac6cd.png
[20370873ebd342f7927f7a569867dd8f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/9b8061a6804e4e869958cb8dd7ca1aff.png
[Link 2]: https://space.bilibili.com/146668655?spm_id_from=333.337.0.0