算法之排序算法-02-排序算法介绍
1，排序算法介绍
什么是排序？
-
排序也叫排序算法（Sort Algorithm），排序是将一组数据按照指定的方式进行排列的过程。
-
排序算法的分类：内部排序和外部排序
-
内部排序：将指定需要处理的数据加载到内存在内存中进行排序的方法（面试最常见）。
-
外部排序：当数据量过大，无法全部加入到内存中的时候，需要借助外部存储器进行排序
-
-
内部排序还可以分为比较排序和非比较排序
-
比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为
非线性时间比较类排序。 -
非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为
线性时间非比较类排序。
-
常见的排序算法(内部排序)
2，排序算法的时间，空间复杂度比较
| 排序算法 | 平均时间复杂度 | 最差时间复杂度 | 最好时间复杂度 | 空间复杂度 | 数据对象稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n^2) | O(n^2) | O(n) | O(1) | 稳定 |
| 选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 数组不稳定、链表稳定 |
| 简单插入排序 | O(n2) | O(n2) | O(n) | O(1) | 稳定 |
| 希尔排序 | O(n*log2n) | O(n2) | O(n) | O(1) | 不稳定 |
| 快速排序 | O(n*log2n) | O(n2) | O(log2n) | O(n*log2n) | 不稳定 |
| 堆排序 | O(n*log2n) | O(n*log2n) | O(n*log2n) | O(1) | 不稳定 |
| 归并排序 | O(n*log2n) | O(n*log2n) | O(n*log2n) | O(n) | 稳定 |
| 计数排序 | O(n+m) | O(n+m) | O(n+m) | O(n+m) | 稳定 |
| 桶排序 | O(n+m) | O(n^2) | O(n) | O(m+m) | 稳定 |
| 基数排序 | O(n*m) | O(n*m) | O(n*m) | O(n+m) | 稳定 |
- 其中，冒泡排序，选择排序，插入排序，希尔排序，快速排序，堆排序，归并排序，都属于基于比较的排序，平均时间复杂度目前最低为：O(nlogn）
- 然而，计数排序，桶排序，基数排序，都不是基于比较的排序，他们是典型的使用空间换时间，有些时候的时间复杂度比O(nlogn)还要低
3 ，相关概念
-
稳定：如果a原本在b前面且a=b，排序之后a仍然在b的前面。
-
不稳定：如果a原本在b的前面且a=b，排序之后 a 可能会出现在 b 的后面。
-
时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
-
空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数