ToB企服应用市场:ToB评测及商务社交产业平台

标题: 排序算法中的冒泡和选择排序详解（持续更新系列） [打印本页]
作者: 河曲智叟    时间: 2023-6-5 12:29
标题: 排序算法中的冒泡和选择排序详解（持续更新系列）
本系列文章为Java基础入门内容，致力于为大家详细讲解学习Java中的一些难点、常见点等，内容由浅入深。
文末有全文重点总结及配套视频资料，更多相关技术问题欢迎和我们一起交流讨论！更多学习资料可点这里获取
前言

我们要想成为一个优秀的程序员，其实非常关键的一点就是要锻炼培养自己的编程思维，就好比一个狙击手，要通过大量的射击训练要用大量的子弹喂出来。
同样的，一个优秀的程序员，他的逻辑和编程思维，也是靠大量的训练锻炼出来的，而这个训练经常是通过各种“算法”来实现的。 所以作为一个从零开始学习的小白，我们必然要学习各种编程算法。这些算法，一方面可以锻炼我们的编程思维，另一方面也是为了完成工作，很多项目中都会或多或少的用到一些算法，并且程序员面试时，算法也是必考的一项。 基于这些因素，接下来会给大家介绍一些经典的算法，比如排序、查找算法，当然还会给大家介绍一些经典的数据结构，比如二叉树、红黑树、图等，那么就请各位认真学习吧。
全文大约【4400】 字，不说废话，只讲可以让你学到技术、明白原理的纯干货！本文带有丰富的案例及配图视频，让你更好地理解和运用文中的技术概念，并可以给你带来具有足够启迪的思考...
一. 排序算法

1. 概念

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

以上排序算法都属于内部排序，也就是只考虑较小数据量且仅需使用内存的排序算法，他们之间关系如下图所示：

因为实际上具体的排序算法非常多，这个是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的位置上。
如果我们把上述的文字描述，转换为图片，则会如下图所示：

这样就完成了第一轮的交换比较。经过第一轮交换后，元素9作为数列中最大的元素，就像是汽水里的气泡一样浮到了最右侧。接着我们继续如此重复上述的比较过程，每一轮结束后，都会有一个本轮最大的元素被移到了最右侧，如下所示：

每一轮的排序结果最终会如上图所示，所以最终的排序结果就是最后一排的数值结果。
最后我们来总结下，冒泡排序算法的3个核心步骤：
这样我们就理解了冒泡排序的实现思路和过程，接下来我们再来看看该如何在Java中通过代码实现冒泡排序。
3. 编码实现

我们根据上述冒泡排序算法的文字描述步骤，利用Java语言进行编程实现，代码如下所示：
  1. public static void bubbleSort(int[] arr) {
  2.     int count = 0;
  3.     for (int i = 0; i < arr.length - 1; i++) {
  4.         for (int j = 0; j < arr.length - 1-i; j++) {
  5.             count++;
  6.             //临时变量 用于交换
  7.             int tmp = 0;
  8.             if (arr[j] > arr[j + 1]) {
  9.                 tmp = arr[j];
  10.                 arr[j] = arr[j + 1];
  11.                 arr[j + 1] = tmp;
  12.             }
  13.         }
  14.     }
  15. }
复制代码
最终执行完上述代码后，arr数组就变成了一个有序的数组。
大家要注意，在上述代码中，bubbleSort方法可以接收一个整数类型的数组arr，通过两层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. 实现思路

按照选择排序的实现原理，接下来再把选择排序的实现思路再细化一下：
但是如何选出最小的一个元素呢？
我们先任意选一个元素，假设它就是最小的元素(默认为无序区间的第一个元素)，然后让这个元素与无序区间中的每一个元素挨个进行比较。 如果遇到比自己小的元素，则更新最小值的下标，直到把无序区间遍历完。最后的那个最小值下标对应的数值，就是该无序区间的最小值。
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). 依次类推，将所有的元素通过不断选择的方式，按有序的方式放到有序区间，最终把整个数组全部排好顺序。
我们把上述选择排序的文字描述内容，变成对应的图片，会如下图所示：




4. 编码实现

接下来也使用Java语言，把选择排序的算法通过编程给大家实现一下：
  1. public static void selectionSort(int[] arr) {
  2.     int count = 0;
  3.     //第一个循环用来遍历数组中的所有数字
  4.     for (int i = 0; i < arr.length; i++) {
  5.         //初始化一个变量，用来记录最小数字的下标。初始默认假设第一个数字就是最小数字
  6.         int minIndex = i;
  7.         //第二个循环，通过比较获取数组中最小的数字的下标
  8.         for (int j = i + 1; j < arr.length; j++) {
  9.             count++;
  10.             //如果找到更小的数字
  11.             if (arr[minIndex] > arr[j]) {
  12.                 //将minIndex变量的值修改为新的最小数字的下标
  13.                 minIndex = j;
  14.             }
  15.         }
  16.         //所有数字一个个比较结束之后，就能确认那个数字最小了。
  17.         //将最小的数字替换到第一个位置，将第一个位置的数字放到最小数字原来的位置，就是一次交换。
  18.         arr[i] = arr[i] + arr[minIndex] - (arr[minIndex] = arr[i]);
  19.     }
  20. }
复制代码
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). 选择排序是一种简单的排序算法，适用于数据量较小的情况。根据时间复杂度分析，选择排序所花费的时间会随着数据量增大按照平方倍数增⻓，数据量越大，排序效率就越低。但是选择排序也有优势，即它的实现思维逻辑特别简单，比较容易理解。
四. 结语

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


  • 冒泡排序属于交换排序算法的一种；
  • 选择排序算法是原地排序算法的一种；
  • 冒泡排序的核心思想是把相邻的元素进行两两比较，当一个元素大于右侧相邻的元素时，就交换它们的位置；当一个元素小于或等于右侧相邻的元素时，则保持位置不变。
  • 选择排序的实现思想，就是不断地从未排序的元素中选择最大(或最小)的元素，放入到已排好序的元素集合中，直到未排序的元素为空。
以上就是我们这期的全部内容啦，关于冒泡和选择排序这两种算法，大家有不明白的问题也欢迎在评论区和我们一起交流讨论！
视频配套资料：戳我

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4