数据结构（十六）排序
排序算法
0. 前言
本来准备自己写，无意间看到一位大佬的博文…大家还是移步吧
推荐一套自己开发的算法演示工具
1. 总结
| 排序方法 | 平均时间复杂度 | 最坏时间复杂度 | 额外空间复杂度 | 稳定性 |
|---|---|---|---|---|
| 简单选择排序 | O( <math> <semantics> <mrow> <msup> <mi> N </mi> <mn> 2 </mn> </msup> </mrow> <annotation encoding="application/x-tex"> N^2 </annotation> </semantics> </math>N2) | O( <math> <semantics> <mrow> <msup> <mi> N </mi> <mn> 2 </mn> </msup> </mrow> <annotation encoding="application/x-tex"> N^2 </annotation> </semantics> </math>N2) | O( <math> <semantics> <mrow> <mn> 1 </mn> </mrow> <annotation encoding="application/x-tex"> 1 </annotation> </semantics> </math>1) | 不稳定 |
| 冒泡排序 | O( <math> <semantics> <mrow> <msup> <mi> N </mi> <mn> 2 </mn> </msup> </mrow> <annotation encoding="application/x-tex"> N^2 </annotation> </semantics> </math>N2) | O( <math> <semantics> <mrow> <msup> <mi> N </mi> <mn> 2 </mn> </msup> </mrow> <annotation encoding="application/x-tex"> N^2 </annotation> </semantics> </math>N2) | O( <math> <semantics> <mrow> <mn> 1 </mn> </mrow> <annotation encoding="application/x-tex"> 1 </annotation> </semantics> </math>1) | 稳定 |
| 直接插入排序 | O( <math> <semantics> <mrow> <msup> <mi> N </mi> <mn> 2 </mn> </msup> </mrow> <annotation encoding="application/x-tex"> N^2 </annotation> </semantics> </math>N2) | O( <math> <semantics> <mrow> <msup> <mi> N </mi> <mn> 2 </mn> </msup> </mrow> <annotation encoding="application/x-tex"> N^2 </annotation> </semantics> </math>N2) | O( <math> <semantics> <mrow> <mn> 1 </mn> </mrow> <annotation encoding="application/x-tex"> 1 </annotation> </semantics> </math>1) | 稳定 |
| 希尔排序 | O( <math> <semantics> <mrow> <msup> <mi> N </mi> <mi> d </mi> </msup> </mrow> <annotation encoding="application/x-tex"> N^d </annotation> </semantics> </math>Nd) | O( <math> <semantics> <mrow> <msup> <mi> N </mi> <mn> 2 </mn> </msup> </mrow> <annotation encoding="application/x-tex"> N^2 </annotation> </semantics> </math>N2) | O( <math> <semantics> <mrow> <mn> 1 </mn> </mrow> <annotation encoding="application/x-tex"> 1 </annotation> </semantics> </math>1) | 不稳定 |
| 堆排序 | O( <math> <semantics> <mrow> <mi> N </mi> <mi> l </mi> <mi> o </mi> <mi> g </mi> <mi> N </mi> </mrow> <annotation encoding="application/x-tex"> NlogN </annotation> </semantics> </math>NlogN) | O( <math> <semantics> <mrow> <mi> N </mi> <mi> l </mi> <mi> o </mi> <mi> g </mi> <mi> N </mi> </mrow> <annotation encoding="application/x-tex"> NlogN </annotation> </semantics> </math>NlogN) | O( <math> <semantics> <mrow> <mn> 1 </mn> </mrow> <annotation encoding="application/x-tex"> 1 </annotation> </semantics> </math>1) | 不稳定 |
| 快速排序 | O( <math> <semantics> <mrow> <mi> N </mi> <mi> l </mi> <mi> o </mi> <mi> g </mi> <mi> N </mi> </mrow> <annotation encoding="application/x-tex"> NlogN </annotation> </semantics> </math>NlogN) | O( <math> <semantics> <mrow> <msup> <mi> N </mi> <mn> 2 </mn> </msup> </mrow> <annotation encoding="application/x-tex"> N^2 </annotation> </semantics> </math>N2) | O( <math> <semantics> <mrow> <mi> l </mi> <mi> o </mi> <mi> g </mi> <mi> N </mi> </mrow> <annotation encoding="application/x-tex"> logN </annotation> </semantics> </math>logN) | 不稳定 |
| 归并排序 | O( <math> <semantics> <mrow> <mi> N </mi> <mi> l </mi> <mi> o </mi> <mi> g </mi> <mi> N </mi> </mrow> <annotation encoding="application/x-tex"> NlogN </annotation> </semantics> </math>NlogN) | O( <math> <semantics> <mrow> <mi> N </mi> <mi> l </mi> <mi> o </mi> <mi> g </mi> <mi> N </mi> </mrow> <annotation encoding="application/x-tex"> NlogN </annotation> </semantics> </math>NlogN) | O(N) | 稳定 |
| 基数排序 | O(P(N+B)) | O(P(N+B)) | O(N+B) | 稳定 |
查看9道真题和解析
