数据结构七大排序算法图解

ゞ浴缸里的玫瑰 2023-09-29 06:27 64阅读 0赞

# 系列文章整合 #

排序是计算机程序设计中一个非常重要的操作，它将一个数据元素（或记录）的任意序列重新排列成一个按关键字有序的序列,在有序的序列中查找元素的效率很高，但是无序序列只能逐一查找，因此，如何进行排序，尤其是高效排序，是一个重要的课题。 所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作

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

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

提示：

> 排序是计算机程序设计中一个非常重要的操作，它将一个数据元素（或记录）的任意序列重新排列成一个按关键字有序的序列,在有序的序列中查找元素的效率很高，但是无序序列只能逐一查找，因此，如何进行排序，尤其是高效排序，是一个重要的课题。

### 文章目录 ###

*  系列文章整合
 *  一、排序的概念及其运用
 *   *  排序的概念
     *  排序的运用
     *  常见的排序算法
 *  二、插入排序动图演示
 *  三、交换排序动图演示
 *  四、选择排序动图演示
 *  五、归并排序动图展示
 *   *  思想
     *  方法
     *  例题
     *  性能分析
     *  总结
 *  六、数据结构中各种排序方法的综合比较
 *   *  时间性能
     *  空间性能
     *  排序方法的稳定性能
     *  排序方法的时间复杂度的下限
     *  总结

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

`提示：本人不喜欢用专业术语来记录知识点，所以接下来会用例题+白话文的方式记录文章：`

# 一、排序的概念及其运用 #

## 排序的概念 ##

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

> **稳定性的意义**：在根据多种属性进行排序时会有巨大的意义。比如我们先对学生按照学号进行了排序，再对学生进行了按照成绩进行排序，此时学号和成绩成为了两种决定因素，如果我们在按照成绩进行排序时，所使用的算法是不具有稳定性的，那么在对成绩排序后，之前根据学号进行的排序就没有意义了，此时就会出现相同成绩，但是学号靠后的在前面，反之，如果我们选择的排序具有稳定性，那么成绩相同，学号靠前的应该在前面。

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

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

区分内外排序：

<table> 
 <thead> 
  <tr> 
   <th>排序类型</th> 
   <th>数据存储</th> 
   <th>访问速度</th> 
   <th>支持的访问形式</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>内排序</td> 
   <td>数据在内存中（数组）</td> 
   <td>快</td> 
   <td>下标随机访问</td> 
  </tr> 
  <tr> 
   <td>外排序</td> 
   <td>数据在磁盘中，数据量很大</td> 
   <td>慢</td> 
   <td>串行访问</td> 
  </tr> 
 </tbody> 
</table>

## 排序的运用 ##

下面就是按价格对手机进行排序：  
![在这里插入图片描述][b46d921b2ca446c59bd112e3cf6835b0.png]  
下面是根据综合得分对大学进行排名：  
![在这里插入图片描述][531de40c98ee4d5ebb76e8325880725c.png]

## 常见的排序算法 ##

![在这里插入图片描述][91274a9c0b0e4c1fb6d7fe54cfe261a5.png]

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

# 二、插入排序动图演示 #

就是一个有序一个无序，从无序那里面取第一个往有序里面也就是（）里面插入，插入之后仍然保证有序，让所有记录都变成有序的  
换句话说就是  
插入排序的基本思想就是往一个有序区间插入一个数据，依旧保持他有序。

[直接插入排序、希尔排序][Link 1]

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

# 三、交换排序动图演示 #

交换排序的基本思想是两两比较待排序记录的关键字，若两个记录的次序相反则交换这两个记录，直到没有反序的记录为止。应用交换排序基本思想的主要排序方法有冒泡排序和快速排序。

[冒泡排序和快速排序][Link 2]

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

# 四、选择排序动图演示 #

选择排序的主要思想是每一趟从待排序列中选取一个关键字值最小的记录，也即第 1 趟从 n 个记录中选取关键字值最小的记录，在第 2 趟中，从剩下的 n-1 个记录中选取关键字值最小的记录，直到整个序列中的记录都选完位置。这样，由选取记录的顺序便可得到按关键字值有序的序列。

[手撕直接选择排序+树形排序+堆排序（代码+动图演示） …][Link 3]

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

# 五、归并排序动图展示 #

归并排序(Merging Sort)是与插人排序、交换排序、选择排序不同的另一类排序方法。归并的含义是将两个或两个以上的有序表合并成一个新的有序表。

## 思想 ##

归并排序的过程基于下列基本思想进行：  
将两个或两个以上的有序子序列 “ 归并 ” 为一个有序序列。

在内部排序中，通常采用的是 2 路归并排序。  
就是将两个位置相邻的记录有序子序列归并为一个记录的有序序列。

*  此处引用网上一张比较经典的 gif 来展示归并排序的整个过程：  
    ![95de880aaf6d8c58280f5ef5a8d9b16d.gif][]

## 方法 ##

将待排序记录 r\[0\] 到 r\[n-1\] 看成是n个长度为1的有序子表，把这些子表依次两两归并，便得到 \[n/2\] 个有序的子表，然后，再把这 \[n/2\] 个有序的子表两两归并，如此重复，直到最后得到一个长度为 n 的有序表为止。

## 例题 ##

![在这里插入图片描述][1503d45c493549c790351b6a7c27c86d.png]

## 性能分析 ##

⑴、时间复杂度为：O(nlog2n)  
⑵、所需辅助空间：O(n)  
⑶ 、算法稳定性：是稳定排序

共需要 log2n 趟

## 总结 ##

就是俩俩为一组比较，小的在前  
第二趟俩组俩组比较，小的在前  
以此类推  
最后结果是升序

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

# 六、数据结构中各种排序方法的综合比较 #

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

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原

序列中，r\[i\]=r\[j\]，且 r\[i\] 在 r\[j\] 之前，而在排序后的序列中，r\[i\] 仍在 r\[j\] 之前，则称这种排序算法是稳定的；否则称为不稳定的。

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

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

## 时间性能 ##

**1、平均的时间性能**  
**时间复杂度为 O(nlog2n)：快速排序、堆排序和归并排序**  
**时间复杂度为 O(n2)：直接插入排序、冒泡排序和简单选择排序**

某算法的时间复杂度为O(n2)，表明该算法的执行时间与O(n2)成正比

**2、当待排记录序列按关键字顺序有序时**  
**直接插入排序和起泡排序能达到 O(n) 的时间复杂度，**  
**快速排序的时间性能蜕化为 O(n2)**

**3.简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。**

## 空间性能 ##

**指的是排序过程中所需的辅助空间大小**

**1、所有的简单排序方法 (包括：直接插入、起泡和简单选择) 和堆排序的空间复杂度为 O(1)**

**2、快速排序为O(log2n)，为递归程序执行过程中，栈所需的辅助空间**

**3、归并排序所需辅助空间最多，其空间复杂度为O(n);**

## 排序方法的稳定性能 ##

**1、快速排序、简单选择排序、堆排序和希尔排序是不稳定的排序方法**

**2、对于不稳定的排序方法，只要能举出一个实例说明即可**

## 排序方法的时间复杂度的下限 ##

**以上链接中讨论的各种排序方法都是基于 “比较关键字” 进行排序的排序方法。**

**可以证明，这类排序法可能达到的最快的时间复杂度为O(nlogn)**

## 总结 ##

这里用张图代替总结  
![在这里插入图片描述][677d0022675a45cbaecbe04e0b84b081.png]

[deb5205e80fd480cb363c8e80c58c157.png]: https://img-blog.csdnimg.cn/deb5205e80fd480cb363c8e80c58c157.png
[b46d921b2ca446c59bd112e3cf6835b0.png]: https://img-blog.csdnimg.cn/b46d921b2ca446c59bd112e3cf6835b0.png
[531de40c98ee4d5ebb76e8325880725c.png]: https://img-blog.csdnimg.cn/531de40c98ee4d5ebb76e8325880725c.png
[91274a9c0b0e4c1fb6d7fe54cfe261a5.png]: https://img-blog.csdnimg.cn/91274a9c0b0e4c1fb6d7fe54cfe261a5.png
[Link 1]: https://rej177.blog.csdn.net/article/details/124421389
[Link 2]: https://rej177.blog.csdn.net/article/details/124329753
[Link 3]: https://rej177.blog.csdn.net/article/details/124466766
[95de880aaf6d8c58280f5ef5a8d9b16d.gif]: https://img-blog.csdnimg.cn/img_convert/95de880aaf6d8c58280f5ef5a8d9b16d.gif
[1503d45c493549c790351b6a7c27c86d.png]: https://img-blog.csdnimg.cn/1503d45c493549c790351b6a7c27c86d.png
[677d0022675a45cbaecbe04e0b84b081.png]: https://img-blog.csdnimg.cn/677d0022675a45cbaecbe04e0b84b081.png