【数据结构与算法】简单排序（冒泡排序、选择排序、插入排序）完整思路，并用代码封装排序函数

川长思鸟来 2022-12-05 10:12 84阅读 0赞

本系列文章【数据结构与算法】所有完整代码已上传 **github**，想要**完整代码**的小伙伴可以直接去那获取，可以的话欢迎点个**Star**哦~下面放上跳转链接

*  [https://github.com/Lpyexplore/structureAndAlgorithm-JS][https_github.com_Lpyexplore_structureAndAlgorithm-JS]

之前的文章，我已经把前端需要了解的**数据结构**都给说了一边，并且我们也都对其进行了封装。现在我们要开始对**排序算法部分**进行讲解，排序算法顾名思义，就是对一堆杂乱无章的数据按照一定的规则将它们有序地排列在一起。

在讲解排序算法时，大致分成两大类，如下图

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xfUFBQ_size_16_color_FFFFFF_t_70_pic_center]  
本文先介绍三种**简单排序**的实现思路以及代码的实现

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xfUFBQ_size_16_color_FFFFFF_t_70_pic_center 1]

>  *  公众号：**前端印象**
>  *  不定时有送书活动，记得关注~
>  *  关注后回复对应文字领取：【面试题】、【前端必看电子书】、【数据结构与算法完整代码】、【前端技术交流群】

### 排序算法——简单排序 ###

*  一、大O表示法
 *  二、冒泡排序
 *  三、选择排序
 *  四、插入排序
 *  五、结束语

# 一、大O表示法 #

**大O表示法**是一种大致表示算法时间复杂度的表示方法，其中，算法的时间复杂度表示的是算法执行过程中代码所需要的基本运算次数。

**问：** 假设现在有5个人，分别为 `A`、`B`、`C`、`D` 、`E`，它们的身高分别为 `165`、`178`、`150`、`180`、`200`，请你找出最高的那个人，并记录比较次数。

我们来说一个特别简单易懂的算法，来了解大O表示法

**答：** 我们先用 `A` 跟 `B` 比较，得 `B` 比 `A` 高 ； 那我们就用 `B` 跟 `C` 比较，得 `C` 比 `B` 矮 ；继续用 `B` 与 `D` 比较，得 `D` 比 `B` 高 ；最后用 `D` 跟 `E` 比较，得 `E` 比 `D` 高。因此，最终得出 `E` 是这五个人里最高得，同时我们记下得比较次数为 **4** 次。

那么同样用这种方法，人数现在设定为 `n`，那么我们最多需要比较得次数就为 `n - 1` 次，此时我们可以将这种算法的时间复杂度就为 `O(n)`

为什么是 `O(n)` 呢？因为在用这种表示方法时，其实是一种模糊的统计方法，我们要遵循以下几个**原则**：

1.  代码运行次数只取最高次项
2.  所有加法项的常数都用1代替
3.  最高次项的常数用1代替

因此当比较次数为 `n - 1` 时，我们要只取最高次项，并且将最高次项的常数项变为 `1`，因此用大O表示法就为 `O(n)`

其它常见的几种大O表示法还有下面几种：

<table> 
 <thead> 
 <tr> 
 <th>符号</th> 
 <th>名称</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td>O(1)</td> 
 <td>常数</td> 
 </tr> 
 <tr> 
 <td>O(log(n))</td> 
 <td>对数</td> 
 </tr> 
 <tr> 
 <td>O(n)</td> 
 <td>线性</td> 
 </tr> 
 <tr> 
 <td>O(nlog(n))</td> 
 <td>线性和对数乘积</td> 
 </tr> 
 <tr> 
 <td>O(n²)</td> 
 <td>平方</td> 
 </tr> 
 <tr> 
 <td>O( 2 n 2^n 2n)</td> 
 <td>指数</td> 
 </tr> 
 </tbody> 
</table>

在之后每种排序算法中，我们都会简单来判断一下它们的时间复杂度，并用大O表示法来表示

# 二、冒泡排序 #

**冒泡排序**是一种最简单粗暴的排序算法，它的排序方式跟它的名字一样，一个个数据往上冒出来。

我们来看一下具体的实现过程（该排序过程为从小到大排序），直接来看个动图

![在这里插入图片描述][20200924093007859.gif_pic_center]  
主要的思路其实就是从最左边开始，依次比较相邻两个元素的大小，若左边的数大于右边的数就进行交换，这样把所有的相邻元素都比较一遍以后，最右边的数就是其中最大的数了。

紧接着又继续从最左边开始，依次比较各个相邻元素，并判断是否需要交换位置，但与第一遍不同的是，最右边的数不需要进行比较，因为它已经是最大的了。因此第二遍比较完后从右往左数第二个数是其中第二大的数。

以此类推，就能将数据按从小到大的顺序排好了

我们来看一下如何封装冒泡排序的函数吧

我们来简单测试一下该方法是否正确

let arr = [45, 66, 1, 19, 34, 80, 2]
    
    console.log(bubbleSort(arr));
    // 打印结果：[1, 2, 19, 34, 45, 66, 80]

接下来，讨论一下冒泡排序的 **比较次数** 和 **交换次数** 如何用大O表示法来表示。

假设一个数组一共有4个数，我们第一次遍历需要比较3次，此时找到一个最大值；第二次遍历只需要将其中3个数进行比较，只需要比较2次，此时找到第二大的值；第三次遍历只需要将剩余的两个数进行比较，只需要比较1次，此时数组排序完毕。如果不明白，可以看一下上面的动图

该种情况的比较次数一共是 `3 + 2 + 1 = 6` 次。那么延伸到普通情况中，一个数组有 `n` 个元素，那么所需要的比较次数一共是 `(n-1) + (n-2) + …… + 2 + 1 = n*(n-1)/2` ，按照大O表示法的规则，我们找到最高次项为 `n²/2`，将其常数项设为1，为 `n²`，因此冒泡排序的**比较次数**用大O表示法为 `O(n²)`

我们再来看看冒泡排序的交换次数如何用大O表示法来表示。很明显，我们也不清楚到底要交换几次，所以我们就假设每两次比较就要交换一次的话，其总的交换次数为 `n*(n-1)/4`，根据大O表示法的规则，我们可以知道**交换次数**用大O表示法也为 `O(n²)`

**总结：**

1.  冒泡排序的比较次数：O(n²)
2.  冒泡排序的交换次数：O(n²)

# 三、选择排序 #

**选择排序**跟冒泡排序非常类似，唯一的区别就是选择排序每次遍历时，将各个元素比较，将最大值或最小值的索引存放在一个变量中，全部比较完了以后，再将该索引上的元素进行就交换。简单来说就是选择排序是每次遍历交换一次，而冒泡排序每次遍历需要交换多次，因此选择排序一般来说是要比冒泡排序效率高一点的。

同样的，我们来看一下选择排序（从小到大排序）的动图展示：

![在这里插入图片描述][20200924103116985.gif_pic_center]  
我们来看一下选择排序的代码封装

我们来测试一下该方法是否正确

let arr = [45, 66, 1, 19, 34, 80, 2]
    
    console.log(selectionSort(arr));
    // 打印结果：[1, 2, 19, 34, 45, 66, 80]

在了解了选择排序与冒泡排序的区别后，我们应该能清楚得知道，选择排序的比较次数跟冒泡排序一样，因此选择排序的**比较次数**用大O表示法表示为 `O(n²)`

选择排序每遍历一次数组，就只需要交换一次数据，因此其**交换次数**用大O表示法表示为 `O(n)`

**总结：**

1.  选择排序的比较次数：O(n²)
2.  选择排序的交换次数：O(n)

# 四、插入排序 #

**插入排序**是一种将指定元素与某个有序区域元素比较并交换位置的排序算法。

我们先简单举个例子，假设现在有这样一个无序数组

![在这里插入图片描述][20200924105849361.png_pic_center]  
首先，我们把索引为0的元素看作区域，该区域是有序的，因为就只有一个元素，怎样排序都是它一个元素，所以就认为它是有序的。

然后我们取出有序区域右边的第一个元素，即索引为1的元素 `67`，存到变量 `temp` 中。然后从有序区域的最右边开始，将元素依次与变量 `temp` 中的元素 `67` 比较，若大于67，则将位置向右移动一格；若小于67，则不需要继续遍历了，因为该区域是有序的。

第一次遍历的动图：  
![在这里插入图片描述][20200924111012410.gif_pic_center]  
此时的有序区域为 `索引0 ~ 索引1` 这部分，所以我们将索引为2的元素取出，跟有序区域的元素比较

第二次遍历的动图：

![在这里插入图片描述][20200924111230415.gif_pic_center]  
此时的有序区域为 `索引0 ~ 索引2` 这部分，所以我们将索引为3的元素取出，跟有序区域的元素比较

第三次遍历的动图：

![在这里插入图片描述][20200924111335103.gif_pic_center]  
此时的有序区域为 `索引0 ~ 索引3` 这部分，所以我们将索引为4的元素取出，跟有序区域的元素比较

第四次遍历的动图：

![在这里插入图片描述][20200924111437657.gif_pic_center]  
此时整个数组都是有序区域了，这就是一个完整的插入排序

接下来我们来封装一个插入排序的函数

function insertionSort(arr) { 
 	// 获取传入数组的长度
 let length = arr.length
 	
 	// 1. 从索引为1的元素开始向后遍历数组
 	for(let i = 1; i < length; i ++) { 
 		// 2. 取出有序区域右边第一个元素
 		let temp = arr[i]
 		let j = i
 		// 3. 从右往左将有序区域内的元素与temp比较
 		while(arr[j - 1] > temp && j > 0) { 
 			arr[j] = arr[j - 1]
 			j --
 		}
 		// 4. 将temp插入到合适的位置
 		arr[j] = temp
 	}
 	
 	// 返回排序后的数组
 	return arr
 }

我们来测试一下该函数是否正确

let arr = [45, 66, 1, 19, 34, 80, 2]
    
    console.log(insertionSort(arr));
    // 打印结果：[1, 2, 19, 34, 45, 66, 80]

插入排序每次遍历时，比较次数和元素的移动次数都是不确定，那我们就按最坏的情况来考虑。

第一次遍历：比较次数为1，元素移动次数为1；  
第二次遍历：比较次数为2，元素移动次数为2；  
……  
第N次遍历：比较次数为N，元素移动次数为N；

所以，插入排序的比较次数为 `1 + 2 + …… + n`，元素的移动次数也和比较次数一样，那么我们对其取个平均值，也就是 `(n² - n)/4`，用大O表示法表示为 `O(n²)`

**总结：**

1.  插入排序的比较次数：O(n²)
2.  插入排序的元素移动次数：O(n²)

# 五、结束语 #

排序算法中的简单排序就已经讲完啦，下一篇文章将讲解三种**高级排序算法**：希尔排序、归并排序、快速排序。

大家可以关注我，之后我还会一直更新别的数据结构与算法的文章来供大家学习，并且我会把这些文章放到【数据结构与算法】这个专栏里，供大家学习使用。

然后大家可以关注一下我的微信公众号：**前端印象**，等这个专栏的文章完结以后，我会把每种数据结构和算法的笔记放到公众号上，大家可以去那获取。

或者也可以去我的github上获取**完整代码**，欢迎大家点个**Star**

*  [https://github.com/Lpyexplore/structureAndAlgorithm-JS][https_github.com_Lpyexplore_structureAndAlgorithm-JS]

我是Lpyexplore，创作不易，喜欢的加个关注，点个收藏，给个赞~

[https_github.com_Lpyexplore_structureAndAlgorithm-JS]: https://github.com/Lpyexplore/structureAndAlgorithm-JS
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xfUFBQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/ded7b06e3b5b462fb4427fe6855f6a80.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xfUFBQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/2ac3dc182c55433c85df54a9703cf1b9.png
[20200924093007859.gif_pic_center]: /images/20221123/738b420add154b49b38cff4c7bdd3c72.png
[20200924103116985.gif_pic_center]: /images/20221123/51379505f706485fa8745517a6c3f423.png
[20200924105849361.png_pic_center]: /images/20221123/ab85d8de9fa04a3e92010ab5008562e1.png
[20200924111012410.gif_pic_center]: /images/20221123/6aa8845534274fd2bce0fd1c379aed2e.png
[20200924111230415.gif_pic_center]: /images/20221123/13cd6f5edc3548e0861af30854c58a93.png
[20200924111335103.gif_pic_center]: /images/20221123/d69a67dfb53e47c89f304e97963a1b86.png
[20200924111437657.gif_pic_center]: /images/20221123/ea41f71815ff4991a60c55e40aab8e9f.png