【数据结构】手撕排序NO.1----排序初识

系统管理员 2024-04-25 20:05 73阅读 0赞

### ![4b034a2676084b6ebc8e6e10875452ae.png][] ###

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

**目录**

一. 前言

二. 排序的概念及运用

2.1 排序的概念

2.2 排序的运用

2.3 常见的排序算法

三. 冒泡and选择排序

3.1 冒泡排序

3.2 选择排序

四. 各大排序算法的复杂度和稳定性

### 一. 前言 ###

从本期开始，我们的数据结构将迎来一个新的篇章：**排序篇**，啪叽啪叽![7c11d59ace74482eb477a467310a6ed3.gif][]

排序是数据结构中非常重要的内容，在后续的内容中，我们会对各种各样的排序算法进行剖析和实现，敬请期待哦![497c53346191490a8613854a85bb839f.gif][]

> **本期要点**
> 
>  *  对排序进行一个整体的认识
>  *  介绍一下两种最简单的排序
>  *  笼统地介绍一下各大排序算法的复杂度和稳定性

### 二. 排序的概念及运用 ###

#### 2.1 排序的概念 ####

**排序：**所谓排序就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是如何使得记录按照要求排列的方法。

**稳定性：**假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r\[i\]=r\[j\]，且r\[i\]在r\[j\]之前，而在排序后的序列中，r\[i\]仍在r\[j\]之前，则称这种排序算法是稳定的；否则称为不稳定的。

**内部排序：**数据元素全部放在内存中的排序。

**外部排序：**数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

#### 2.2 排序的运用 ####

在日常生活中，我们可以找到许多和排序有关的场景。例如我们进入电脑磁盘右键就可以看到一个排序方式的选项，这是对我们电脑的磁盘文件进行排序，你可以根据需求选择不同排序方式进行排序![1b7c7e88ba8c410796cf0b13ceb1b27e.png][]

![f05f789dcc444879b13cf337ea32aed5.png][]

又或者，随便打开一个网购网站/软件，例如京东，我们可以看到左上角就可以对商品的某一维度进行排序![1b7c7e88ba8c410796cf0b13ceb1b27e.png][]

![6f201393bcd648c68152d6837fd7ede4.png][]

再或者，世界500强榜单也是经过排序后产生的![1b7c7e88ba8c410796cf0b13ceb1b27e.png][]

![ab5317a3c8f642efaded2c2b89a25a3f.png][]

> 总之，无论是在计算机的学习上还是现实生活中，排序都是非常重要的主题，其运用十分广泛，它无处不在![7738c0f5faca4efca8c9fbd6ac205cc7.gif][]

#### 2.3 常见的排序算法 ####

排序算法分为比较类排序和非比较类排序，如下图所示：

![172926218f4c4a35bdad0fd41a5338b7.png][]

### 三. 冒泡and选择排序 ###

> 本期我们先介绍一下我们的两个老朋友：冒泡排序和选择排序![239cc787314849199c0ba78894e9b3e4.png][]

#### 3.1 冒泡排序 ####

*  **思想 :** 在一个序列中，每次对序列中的相邻记录的键值大小进行比较，将较大(升序)或较小(降序)的记录向后移动。如此循环，大/小的记录会慢慢“浮”到序列的后端，整个过程就像是冒泡一样，顾称之为冒泡排序。
 *  **冒泡过程：**以下是对某个序列进行冒泡排序的过程

![6293af774f6e4fefb24d2428b1a6cbae.png][]

> 可以看出，对于上面具有5个元素的无序数组，我们通过4趟的冒泡后就将其变为有序数组，每一趟冒泡后都可以使最大的数沉底。

*  **动图演示：**我们可以通过一下动图感受一下冒泡两两比较的过程：

![6169883938e94a3d879a403a2b3223fd.gif][]

* **循环控制：**很明显，我们需要两层循环来控制冒泡排序的过程。内层循环控制当前趟的数据交换，外层循环控制冒泡排序的趟数。
 * **外层循环结束条件：**由于每一趟结束后都有一个数冒到序列后端，因此对于N个数的序列来说，一共需要N-1趟(只剩一个数不需要冒泡)。
 
 for (int i = 0; i < n - 1; i++) //外层循环，N-1趟
 	{
 ; 
 	}
 * **内层循环结束条件：**内层循环用于数据的比较。已知N个数据共需比较N-1次，由于每一趟结束后就有数据到正确的位置，下一趟需要比较的数据个数就会少1，因此每趟的比较次数随着趟数的增加呈递减趋势，初始为N-1次。
 
 for (int i = 0; i < n - 1; i++) //外层循环，N-1趟
 	{
 		for (int j = 0; j < n - 1 - i; j++) //内层循环，次数随趟数增加而递减，初始为N-1
 		{
 ;
 		}
 	}
 * **完整代码：**
 
 void swap(int* p1, int* p2)
 {
 	int tmp = *p1;
 	*p1 = *p2;
 	*p2 = tmp;
 }
 void BubblingSort(int* a, int n)
 {
 
 	for (int i = 0; i < n - 1; i++) //外层循环，N-1趟
 	{
 		for (int j = 0; j < n - 1 - i; j++) //内层循环，次数随趟数增加而递减，初始为N-1
 		{
 			if (a[j] > a[j + 1]) //升序排列，较大的往后移
 			{
 				swap(&a[j], &a[j + 1]); //交换
 			}
 		}
 	}
 }
 * **改进优化：**上面的代码还存在着改进空间，我们来看下面两个情景：

![ec701bba64614ad0810a9a8fe25a4d1c.png][]

> 对于情境1，我们只需一趟冒泡即可让数组有序，而如果按照上面的代码，我们依旧要进行4趟的冒泡，即有三趟是无效的。
> 
> 而情境1就更夸张了，数组已经有序，我们却傻乎乎的做了4趟无效冒泡。无疑是非常浪费时间的。
> 
> --------------------
> 
> 考虑到这些情况，我们提出了优化方案：在每趟结束后判断一下当前趟是否发生了元素交换，如果没有，则说明序列已经有序了，及时止损，反之继续。优化后的代码如下：
> 
> void swap(int* p1, int* p2)
> {
> 	int tmp = *p1;
> 	*p1 = *p2;
> 	*p2 = tmp;
> }
> 
> void BubblingSort(int* a, int n)
> {
> 	for (int i = 0; i < n - 1; i++) //外层循环，N-1趟
> 	{
> int flag=0; //标识每一趟是否发生交换 0：没有 1：有
> 		for (int j = 0; j < n - 1 - i; j++) //内层循环，次数随趟数增加而递减，初始为N-1
> 		{
> 			if (a[j] > a[j + 1]) //升序排列，较大的往后移
> 			{
> 				swap(&a[j], &a[j + 1]); //交换
> flag = 1;
> 			}
> 		}
> //判断是否已经有序
> if(flag == 0)
> {
> break; //有序则退出循环
> }
> 	}
> }

*  **时间/空间复杂度：**结合上面的图片和代码我们可以看出，总共N-1趟，每趟N-1，N-2...次比较，共比较 (N-1) + (N-2) + (N-3) + (N-4) + (N-5) + ...... + 1次，时间复杂度为![O(N^\{2\})][O_N_2]；而由于没有额外的辅助空间，空间复杂度为![O(1)][O_1]。
 *  **稳定性分析：**由于我们是将较大的或较小的进行交换，当两个数相等时并不会进行交换，因而不会改变相同元素的先后次序，所以冒泡排序是稳定的排序。

#### 3.2 选择排序 ####

*  **思想 :** 每一次从待排序的数据元素中选出最小(升序)或最大(降序)的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
 *  **选择过程：**以下是对某个序列进行选择排序的过程：

![658e98662dad44119c349b922276447e.png][] **动图演示：**我们一样通过动图感受一下选择排序的过程： ![ad6dce836bdf4156954b4bf75ddddd4c.gif][]

* **循环控制：**类似的，我们需要两层循环来控制选择排序的过程。内层循环遍历序列找出最大/最小值，外层循环控制选择的次数。
 * **外层循环结束条件：**每一次遍历完都可以选出一个数换到起始位置，一共N个数，故要选N-1次(最后一个数不需要选择)
 
 for (int i = 0; i < n-1; i++) //外层循环，共要选择n-1次
 	{
 ;
 	}
 * **内层循环结束条件：**内层循环通过比较进行选数，一开始N个数需要比较N-1次，然后每趟结束后下一次选择的起始位置就往后移动一位，比较次数减1
 
 for (int i = 0; i < n-1; i++) //外层循环，共选择n-1次
 	{
 		for (int j = i + 1; j < n; j++) //内层循环，起始位置开始向后进行比较，选最小值
 		{
 ;
 		}
 	}
 * **完整代码：**
 
 void swap(int* p1, int* p2)
 {
 	int tmp = *p1;
 	*p1 = *p2;
 	*p2 = tmp;
 }
 void SelectSort(int* a, int n)
 {
 	for (int i = 0; i < n-1; i++) //外层循环，共选择n-1次
 	{
 		int mini = i; //记录最小值的下标，初始为第一个数下标
 		for (int j = i + 1; j < n; j++) //内层循环，起始位置开始向后进行比较，选最小值
 		{
 			if (a[mini] > a[j]) //比最小值小，交换下标
 			{
 				mini = j;
 			}
 		}
 		swap(&a[mini], &a[i]); //将最小值与起始位置的数据互换
 	}
 }
 * **时间/空间复杂度：**一共选了N-1次，每次选择需要比较N-1，N-2，N-3...次，加起来和冒泡一样时间复杂度为![O(N)][O_N]；没有用到辅助空间，空间复杂度为![O(1)][O_1]
 * **稳定性分析：**由于是选数交换，在交换的过程中很可能会打乱相同元素的顺序，例如下面这个例子：![e9e1e3b348424a5c97c2a546c721c0aa.png][]

我们发现，在第一趟交换中，**黑5**被交换到了**红5**后面，在整个排序结束后，**黑5**依然在**红5**的后方，与最开始的顺序不一致。由此我们可以得出，选择排序是不稳定的排序。

### 四. 各大排序算法的复杂度和稳定性 ###

废话不多说，直接上表：

<table style="width:650px;"> 
 <thead> 
 <tr> 
 <th style="text-align:center;width:105px;">排序算法</th> 
 <th style="text-align:center;width:90px;">时间复杂度(最好)</th> 
 <th style="text-align:center;width:95px;">时间复杂度(平均)</th> 
 <th style="text-align:center;width:93px;">时间复杂度(最坏)</th> 
 <th style="text-align:center;width:93px;">空间复杂度</th> 
 <th style="text-align:center;width:74px;">稳定性</th> 
 <th style="width:98px;"> 数据敏感度 </th> 
 </tr> 
 <tr> 
 <th colspan="7" style="background-color:#ffffcc;text-align:center;">比较类排序</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td style="width:105px;">冒泡排序</td> 
 <td style="width:90px;"><img alt="O(N)" src="https://latex.csdn.net/eq?O%28N%29"></td> 
 <td style="width:95px;"><img alt="O(N^{2})" src="https://latex.csdn.net/eq?O%28N%5E%7B2%7D%29"></td> 
 <td style="width:93px;"><img alt="O(N^{2})" src="https://latex.csdn.net/eq?O%28N%5E%7B2%7D%29"></td> 
 <td style="width:93px;"><img alt="O(1)" src="https://latex.csdn.net/eq?O%281%29"></td> 
 <td style="width:74px;">稳定</td> 
 <td style="width:98px;">强</td> 
 </tr> 
 <tr> 
 <td style="width:105px;">选择排序</td> 
 <td style="width:90px;"><img alt="O(N^{2})" src="https://latex.csdn.net/eq?O%28N%5E%7B2%7D%29"></td> 
 <td style="width:95px;"><img alt="O(N^{2})" src="https://latex.csdn.net/eq?O%28N%5E%7B2%7D%29"></td> 
 <td style="width:93px;"><img alt="O(N^{2})" src="https://latex.csdn.net/eq?O%28N%5E%7B2%7D%29"></td> 
 <td style="width:93px;"><img alt="O(1)" src="https://latex.csdn.net/eq?O%281%29"></td> 
 <td style="width:74px;">不稳定</td> 
 <td style="width:98px;">弱</td> 
 </tr> 
 <tr> 
 <td style="width:105px;">直接插入排序</td> 
 <td style="width:90px;"><img alt="O(N)" src="https://latex.csdn.net/eq?O%28N%29"></td> 
 <td style="width:95px;"><img alt="O(N^{2})" src="https://latex.csdn.net/eq?O%28N%5E%7B2%7D%29"></td> 
 <td style="width:93px;"><img alt="O(N^{2})" src="https://latex.csdn.net/eq?O%28N%5E%7B2%7D%29"></td> 
 <td style="width:93px;"><img alt="O(1)" src="https://latex.csdn.net/eq?O%281%29"></td> 
 <td style="width:74px;">稳定</td> 
 <td style="width:98px;">强</td> 
 </tr> 
 <tr> 
 <td style="width:105px;">希尔排序</td> 
 <td style="width:90px;"><img alt="O(N^{1.3})" src="https://latex.csdn.net/eq?O%28N%5E%7B1.3%7D%29"></td> 
 <td style="width:95px;"> <img alt="O(NlogN)" src="https://latex.csdn.net/eq?O%28NlogN%29"> <img alt="\sim O(N^{2})" src="https://latex.csdn.net/eq?%5Csim%20O%28N%5E%7B2%7D%29"> </td> 
 <td style="width:93px;"><img alt="O(N^{2})" src="https://latex.csdn.net/eq?O%28N%5E%7B2%7D%29"></td> 
 <td style="width:93px;"><img alt="O(1)" src="https://latex.csdn.net/eq?O%281%29"></td> 
 <td style="width:74px;">不稳定</td> 
 <td style="width:98px;">强</td> 
 </tr> 
 <tr> 
 <td style="width:105px;">堆排序</td> 
 <td style="width:90px;"><img alt="O(NlogN)" src="https://latex.csdn.net/eq?O%28NlogN%29"></td> 
 <td style="width:95px;"><img alt="O(NlogN)" src="https://latex.csdn.net/eq?O%28NlogN%29"></td> 
 <td style="width:93px;"><img alt="O(NlogN)" src="https://latex.csdn.net/eq?O%28NlogN%29"></td> 
 <td style="width:93px;"><img alt="O(1)" src="https://latex.csdn.net/eq?O%281%29"></td> 
 <td style="width:74px;">不稳定</td> 
 <td style="width:98px;">弱</td> 
 </tr> 
 <tr> 
 <td style="width:105px;">快速排序</td> 
 <td style="width:90px;"><img alt="O(NlogN)" src="https://latex.csdn.net/eq?O%28NlogN%29"></td> 
 <td style="width:95px;"><img alt="O(NlogN)" src="https://latex.csdn.net/eq?O%28NlogN%29"></td> 
 <td style="width:93px;"><img alt="O(N^{2})" src="https://latex.csdn.net/eq?O%28N%5E%7B2%7D%29"></td> 
 <td style="width:93px;"><img alt="O(1)" src="https://latex.csdn.net/eq?O%281%29"></td> 
 <td style="width:74px;">不稳定</td> 
 <td style="width:98px;">强</td> 
 </tr> 
 <tr> 
 <td style="width:105px;">归并排序</td> 
 <td style="width:90px;"><img alt="O(NlogN)" src="https://latex.csdn.net/eq?O%28NlogN%29"></td> 
 <td style="width:95px;"><img alt="O(NlogN)" src="https://latex.csdn.net/eq?O%28NlogN%29"></td> 
 <td style="width:93px;"><img alt="O(NlogN)" src="https://latex.csdn.net/eq?O%28NlogN%29"></td> 
 <td style="width:93px;"><img alt="O(N)" src="https://latex.csdn.net/eq?O%28N%29"></td> 
 <td style="width:74px;">稳定</td> 
 <td style="width:98px;">弱</td> 
 </tr> 
 <tr> 
 <td colspan="7" style="background-color:#ffffcc;text-align:center;">非比较类排序</td> 
 </tr> 
 <tr> 
 <td style="width:105px;">基数排序</td> 
 <td style="width:90px;"><img alt="O(N\times K)" src="https://latex.csdn.net/eq?O%28N%5Ctimes%20K%29"></td> 
 <td style="width:95px;"><img alt="O(N\times K)" src="https://latex.csdn.net/eq?O%28N%5Ctimes%20K%29"></td> 
 <td style="width:93px;"><img alt="O(N\times K)" src="https://latex.csdn.net/eq?O%28N%5Ctimes%20K%29"></td> 
 <td style="width:93px;"><img alt="O(N+K)" src="https://latex.csdn.net/eq?O%28N&amp;plus;K%29"></td> 
 <td style="width:74px;">稳定</td> 
 <td style="width:98px;">弱</td> 
 </tr> 
 <tr> 
 <td style="width:105px;">桶排序</td> 
 <td style="width:90px;"><img alt="O(N)" src="https://latex.csdn.net/eq?O%28N%29"></td> 
 <td style="width:95px;"><img alt="O(N+K)" src="https://latex.csdn.net/eq?O%28N&amp;plus;K%29"></td> 
 <td style="width:93px;"><img alt="O(N^{2})" src="https://latex.csdn.net/eq?O%28N%5E%7B2%7D%29"></td> 
 <td style="width:93px;"><img alt="O(N+K)" src="https://latex.csdn.net/eq?O%28N&amp;plus;K%29"></td> 
 <td style="width:74px;">稳定</td> 
 <td style="width:98px;">强</td> 
 </tr> 
 <tr> 
 <td style="width:105px;">计数排序</td> 
 <td style="width:90px;"><img alt="O(N+K)" src="https://latex.csdn.net/eq?O%28N&amp;plus;K%29"></td> 
 <td style="width:95px;"><img alt="O(N+K)" src="https://latex.csdn.net/eq?O%28N&amp;plus;K%29"></td> 
 <td style="width:93px;"><img alt="O(N+K)" src="https://latex.csdn.net/eq?O%28N&amp;plus;K%29"></td> 
 <td style="width:93px;"><img alt="O(K)" src="https://latex.csdn.net/eq?O%28K%29"></td> 
 <td style="width:74px;">稳定</td> 
 <td style="width:98px;"> 弱 </td> 
 </tr> 
 </tbody> 
</table>

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

***以上，就是本期的全部内容啦*****?**

***制作不易，能否点个赞再走呢*****?**

[4b034a2676084b6ebc8e6e10875452ae.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/cb4f7ca96f974c3b9c2f304aae5ff95a.png
[7c11d59ace74482eb477a467310a6ed3.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/17a0caa6f4dd4398bd349547426870af.gif
[497c53346191490a8613854a85bb839f.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/898afb2acd52414488a44671d9395fed.gif
[1b7c7e88ba8c410796cf0b13ceb1b27e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/594b789a69a740edb4d9be5a06dc6bb7.png
[f05f789dcc444879b13cf337ea32aed5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/45a1f9630e6244e192fb152892394fde.png
[6f201393bcd648c68152d6837fd7ede4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/af06f94d7ded4d53ae09d1bfe7ead295.png
[ab5317a3c8f642efaded2c2b89a25a3f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/e6c5d3dda9b64fcbace3957eafddc629.png
[7738c0f5faca4efca8c9fbd6ac205cc7.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/ff2637b3068640e4a2b04e6de6fa41ce.gif
[172926218f4c4a35bdad0fd41a5338b7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/20d0018e1639437b9d7da6f6990dcac3.png
[239cc787314849199c0ba78894e9b3e4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/920923a65e114618bed56536bd359023.png
[6293af774f6e4fefb24d2428b1a6cbae.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/1383fe9c49664baf91bd86dfb96f7d2c.png
[6169883938e94a3d879a403a2b3223fd.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/378b11f3222741feb96da108f895f186.gif
[ec701bba64614ad0810a9a8fe25a4d1c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/fecb863f76454cd88d8f47989279c68b.png
[O_N_2]: https://latex.csdn.net/eq?O%28N%5E%7B2%7D%29
[O_1]: https://latex.csdn.net/eq?O%281%29
[658e98662dad44119c349b922276447e.png]: https://img-blog.csdnimg.cn/658e98662dad44119c349b922276447e.png
[ad6dce836bdf4156954b4bf75ddddd4c.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/c90b6e58aae24a4a93ea566d8a5c76a6.gif
[O_N]: https://latex.csdn.net/eq?O%28N%29
[e9e1e3b348424a5c97c2a546c721c0aa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/25/0533c2310c6a4b88ac79b70ade3ce015.png