排序算法经过长时间演变，大体可以分为两类：内排序和外排序。在排序过程中，全部记录存放在内存，则成为内排序；如果排序过程中需要使用外存，则称为外排序。
我们通常所说的排序算法往往指的是内部排序算法，即数据记录在内存中进行排序。
排序算法大体可分为两种：
一种是比较排序，时间复杂度o(nlogn) ~ o(n^2)，主要有：冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序等。
另一种是非比较排序，时间复杂度可以达到o(n)，主要有：计数排序，基数排序，桶排序等。
内排序有可以分为以下几类：
（1）插入排序：直接插入排序、二分法插入排序、希尔排序
（2）选择排序：直接选择排序、堆排序
（3）交换排序：冒泡排序、快速排序
（4）归并排序
（5）基数排序
| 排序方法 | 时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 | 复杂性 |
|---|---|---|---|---|---|---|
| 插入排序 | o(n2) | o(n2) | o(n) | o(1) | 稳定 | 简单 |
| 希尔排序 | o(nlog2n) | o(n2) | o(n1.3) | o(1) | 不稳定 | 较复杂 |
| 选择排序 | o(n2) | o(n2) | o(n2) | o(1) | 不稳定 | 简单 |
| 堆排序 | o(nlog2n) | o(nlog2n) | o(nlog2n) | o(1) | 不稳定 | 较复杂 |
| 冒泡排序 | o(n2) | o(n2) | o(n) | o(1) | 稳定 | 简单 |
| 快速排序 | o(nlog2n) | o(n2) | o(nlog2n) | o(nlog2n) | 不稳定 | 较复杂 |
| 归并排序 | o(nlog2n) | o(nlog2n) | o(nlog2n) | o(n) | 稳定 | 较复杂 |
| 基数排序 | o(d(n r)) | o(d(n r)) | o(d(n r)) | o(n r) | 稳定 | 较复杂 |
排序算法专业术语解释
1、稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 仍然在 b 的前面，则为稳定排序。
2、非稳定排序：如果 a 原本在 b 的前面，且 a == b，排序之后 a 可能不在 b 的前面，则为非稳定排序。
3、原地排序：原地排序就是指在排序过程中不申请多余的存储空间，只利用原来存储待排数据的存储空间进行比较和交换的数据排序。
4、非原地排序：需要利用额外的数组来辅助排序。
5、时间复杂度：一个算法执行所消耗的时间。
6、空间复杂度：运行完一个算法所需的内存大小。