数据结构（十六）排序

Love The Way You Lie 2022-04-15 06:10 102阅读 0赞

## 排序算法 ##

### 0. 前言 ###

本来准备自己写，无意间看到一位大佬的博文…大家还是移步吧  
[推荐一套自己开发的算法演示工具][Link 1]

### 1. 总结 ###

<table> 
 <thead> 
  <tr> 
   <th>排序方法</th> 
   <th>平均时间复杂度</th> 
   <th>最坏时间复杂度</th> 
   <th>额外空间复杂度</th> 
   <th>稳定性</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>简单选择排序</td> 
   <td>O(<span><span><span> N 2 N^2 </span><span><span><span style="height: 0.814108em; vertical-align: 0em;"></span><span><span style="margin-right: 0.10903em;">N</span><span><span><span><span style="height: 0.814108em;"><span style="top: -3.063em; margin-right: 0.05em;"><span style="height: 2.7em;"></span><span><span>2</span></span></span></span></span></span></span></span></span></span></span></span>)</td> 
   <td>O(<span><span><span> N 2 N^2 </span><span><span><span style="height: 0.814108em; vertical-align: 0em;"></span><span><span style="margin-right: 0.10903em;">N</span><span><span><span><span style="height: 0.814108em;"><span style="top: -3.063em; margin-right: 0.05em;"><span style="height: 2.7em;"></span><span><span>2</span></span></span></span></span></span></span></span></span></span></span></span>)</td> 
   <td>O(<span><span><span> 1 1 </span><span><span><span style="height: 0.64444em; vertical-align: 0em;"></span><span>1</span></span></span></span></span>)</td> 
   <td>不稳定</td> 
  </tr> 
  <tr> 
   <td>冒泡排序</td> 
   <td>O(<span><span><span> N 2 N^2 </span><span><span><span style="height: 0.814108em; vertical-align: 0em;"></span><span><span style="margin-right: 0.10903em;">N</span><span><span><span><span style="height: 0.814108em;"><span style="top: -3.063em; margin-right: 0.05em;"><span style="height: 2.7em;"></span><span><span>2</span></span></span></span></span></span></span></span></span></span></span></span>)</td> 
   <td>O(<span><span><span> N 2 N^2 </span><span><span><span style="height: 0.814108em; vertical-align: 0em;"></span><span><span style="margin-right: 0.10903em;">N</span><span><span><span><span style="height: 0.814108em;"><span style="top: -3.063em; margin-right: 0.05em;"><span style="height: 2.7em;"></span><span><span>2</span></span></span></span></span></span></span></span></span></span></span></span>)</td> 
   <td>O(<span><span><span> 1 1 </span><span><span><span style="height: 0.64444em; vertical-align: 0em;"></span><span>1</span></span></span></span></span>)</td> 
   <td>稳定</td> 
  </tr> 
  <tr> 
   <td>直接插入排序</td> 
   <td>O(<span><span><span> N 2 N^2 </span><span><span><span style="height: 0.814108em; vertical-align: 0em;"></span><span><span style="margin-right: 0.10903em;">N</span><span><span><span><span style="height: 0.814108em;"><span style="top: -3.063em; margin-right: 0.05em;"><span style="height: 2.7em;"></span><span><span>2</span></span></span></span></span></span></span></span></span></span></span></span>)</td> 
   <td>O(<span><span><span> N 2 N^2 </span><span><span><span style="height: 0.814108em; vertical-align: 0em;"></span><span><span style="margin-right: 0.10903em;">N</span><span><span><span><span style="height: 0.814108em;"><span style="top: -3.063em; margin-right: 0.05em;"><span style="height: 2.7em;"></span><span><span>2</span></span></span></span></span></span></span></span></span></span></span></span>)</td> 
   <td>O(<span><span><span> 1 1 </span><span><span><span style="height: 0.64444em; vertical-align: 0em;"></span><span>1</span></span></span></span></span>)</td> 
   <td>稳定</td> 
  </tr> 
  <tr> 
   <td>希尔排序</td> 
   <td>O(<span><span><span> N d N^d </span><span><span><span style="height: 0.849108em; vertical-align: 0em;"></span><span><span style="margin-right: 0.10903em;">N</span><span><span><span><span style="height: 0.849108em;"><span style="top: -3.063em; margin-right: 0.05em;"><span style="height: 2.7em;"></span><span><span>d</span></span></span></span></span></span></span></span></span></span></span></span>)</td> 
   <td>O(<span><span><span> N 2 N^2 </span><span><span><span style="height: 0.814108em; vertical-align: 0em;"></span><span><span style="margin-right: 0.10903em;">N</span><span><span><span><span style="height: 0.814108em;"><span style="top: -3.063em; margin-right: 0.05em;"><span style="height: 2.7em;"></span><span><span>2</span></span></span></span></span></span></span></span></span></span></span></span>)</td> 
   <td>O(<span><span><span> 1 1 </span><span><span><span style="height: 0.64444em; vertical-align: 0em;"></span><span>1</span></span></span></span></span>)</td> 
   <td>不稳定</td> 
  </tr> 
  <tr> 
   <td>堆排序</td> 
   <td>O(<span><span><span> N l o g N NlogN </span><span><span><span style="height: 0.88888em; vertical-align: -0.19444em;"></span><span style="margin-right: 0.10903em;">N</span><span style="margin-right: 0.01968em;">l</span><span>o</span><span style="margin-right: 0.03588em;">g</span><span style="margin-right: 0.10903em;">N</span></span></span></span></span>)</td> 
   <td>O(<span><span><span> N l o g N NlogN </span><span><span><span style="height: 0.88888em; vertical-align: -0.19444em;"></span><span style="margin-right: 0.10903em;">N</span><span style="margin-right: 0.01968em;">l</span><span>o</span><span style="margin-right: 0.03588em;">g</span><span style="margin-right: 0.10903em;">N</span></span></span></span></span>)</td> 
   <td>O(<span><span><span> 1 1 </span><span><span><span style="height: 0.64444em; vertical-align: 0em;"></span><span>1</span></span></span></span></span>)</td> 
   <td>不稳定</td> 
  </tr> 
  <tr> 
   <td>快速排序</td> 
   <td>O(<span><span><span> N l o g N NlogN </span><span><span><span style="height: 0.88888em; vertical-align: -0.19444em;"></span><span style="margin-right: 0.10903em;">N</span><span style="margin-right: 0.01968em;">l</span><span>o</span><span style="margin-right: 0.03588em;">g</span><span style="margin-right: 0.10903em;">N</span></span></span></span></span>)</td> 
   <td>O(<span><span><span> N 2 N^2 </span><span><span><span style="height: 0.814108em; vertical-align: 0em;"></span><span><span style="margin-right: 0.10903em;">N</span><span><span><span><span style="height: 0.814108em;"><span style="top: -3.063em; margin-right: 0.05em;"><span style="height: 2.7em;"></span><span><span>2</span></span></span></span></span></span></span></span></span></span></span></span>)</td> 
   <td>O(<span><span><span> l o g N logN </span><span><span><span style="height: 0.88888em; vertical-align: -0.19444em;"></span><span style="margin-right: 0.01968em;">l</span><span>o</span><span style="margin-right: 0.03588em;">g</span><span style="margin-right: 0.10903em;">N</span></span></span></span></span>)</td> 
   <td>不稳定</td> 
  </tr> 
  <tr> 
   <td>归并排序</td> 
   <td>O(<span><span><span> N l o g N NlogN </span><span><span><span style="height: 0.88888em; vertical-align: -0.19444em;"></span><span style="margin-right: 0.10903em;">N</span><span style="margin-right: 0.01968em;">l</span><span>o</span><span style="margin-right: 0.03588em;">g</span><span style="margin-right: 0.10903em;">N</span></span></span></span></span>)</td> 
   <td>O(<span><span><span> N l o g N NlogN </span><span><span><span style="height: 0.88888em; vertical-align: -0.19444em;"></span><span style="margin-right: 0.10903em;">N</span><span style="margin-right: 0.01968em;">l</span><span>o</span><span style="margin-right: 0.03588em;">g</span><span style="margin-right: 0.10903em;">N</span></span></span></span></span>)</td> 
   <td>O(N)</td> 
   <td>稳定</td> 
  </tr> 
  <tr> 
   <td>基数排序</td> 
   <td>O(P(N+B))</td> 
   <td>O(P(N+B))</td> 
   <td>O(N+B)</td> 
   <td>稳定</td> 
  </tr> 
 </tbody> 
</table>

### 2. 各种排序算法比较 ###

[《数据结构》09-排序1 排序][09-_1]

[Link 1]: https://blog.csdn.net/qq_31116753/article/details/84076734
[09-_1]: https://blog.csdn.net/liyuanyue2017/article/details/84325540

发表评论取消回复

表情：

评论列表（有 0 条评论，102人围观）

还没有评论，来说两句吧...

相关阅读

相关数据结构题目收录（十六）

1、处理冲突的方法有\_\_\_\_。 A：线性探测法 B：除留余数法 C：链地址法 D：折叠法解析处理冲突的方法： 1、开放地址

╰半夏微凉°/ 2024年04月03日 12:32/ 0 赞/ 42 阅读

相关数据结构实验六排序

数据结构实验六排序背景知识：各种排序方法目的要求１．掌握常见的排序算法的思想及其适用条件。２．掌握常见的排序算法的程序实现。实验内容：输

今天药忘吃喽~/ 2022年08月23日 00:54/ 0 赞/ 143 阅读

相关复习数据结构：排序算法（六）——堆排序

对于堆排序，前面一篇博文中已经复习到了堆排序，这里就简单介绍一下，并给出核心部分的解释。堆排序是一种不稳定的排序，也是内排序。时间复杂度为O(nlogn

淡淡的烟草味﹌/ 2022年08月07日 01:56/ 0 赞/ 156 阅读

相关【python】python数据结构（六）——排序：插入排序

算法说明时间复杂度O(n^2) 不稳定代码 coding=utf-8 def insert_sort(lst):

左手的ㄟ右手/ 2022年06月06日 01:23/ 0 赞/ 175 阅读

相关数据结构(十四)归并排序

1、分解将待排序数组A\[1..n\]分成两个各含n/2个元素的子序列，然后对这个两个子序列进行递归排序，最后将这两个已排序的子序列进行合并，即得到最终排好序的序列：

拼搏现实的明天。/ 2022年05月31日 11:39/ 0 赞/ 180 阅读

相关数据结构（十六）排序

排序算法 0. 前言本来准备自己写，无意间看到一位大佬的博文…大家还是移步吧 [推荐一套自己开发的算法演示工具][Link 1] 1. 总结 <tab

Love The Way You Lie/ 2022年04月15日 06:10/ 0 赞/ 103 阅读

相关数据结构（十）：直接插入排序

直接插入排序是将未排序的数据插入至已排好序序列的合适位置直接插入排序例子流程：首先比较数组的前两个数据，并排序

た入场券/ 2021年10月01日 11:00/ 0 赞/ 312 阅读

相关数据结构（十二）：快速排序

通过一趟排序将待排序元素分割成独立的两部分，其中一部分元素的值均比另一部分的值小，则分别对这两部分继续进行排序，直到整个序列有序直接插入排序例子流程：

迈不过友情╰/ 2021年09月30日 11:16/ 0 赞/ 244 阅读

相关数据结构（六）：排序（二）

文章目录前言一、快速排序 1.单趟排序（1）左右哨兵法（2）挖坑法 2.非递归实现

今天药忘吃喽~/ 2021年09月08日 01:02/ 0 赞/ 314 阅读

相关数据结构（六）：排序（一）

文章目录一、排序的相关概念二、直接插入排序二、希尔排序三、选择排序四、堆排序五、冒泡排序感谢阅读，如有错误请批评指

落日映苍穹つ/ 2021年09月07日 21:36/ 0 赞/ 260 阅读