排序算法分类
(一)
- 内部排序和外部排序
（二）
- 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。(非线性时间)
- 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。 (线性时间)
（三）
- 非线性时间比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序。如：快速排序、归并排序、堆排序、冒泡排序等。在排序的最终结果里，元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较，才能确定自己的位置。
- 线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。如：计数排序、基数排序、桶排序。非比较排序是通过确定每个元素之前，应该有多少个元素来排序。针对数组arr，计算arr之前有多少个元素，则唯一确定了arr在排序后数组中的位置。
（四）
- 比较类排序
- 交换排序 (swap)
- 冒泡排序 (bubble Sort) - 双重遍历，相邻元素两两比较交换
- 快速排序 (quick Sort) - 较复杂
- 插入排序 (insertion)
- 简单插入排序 (insertion sort) - 分左右两批，遍历有序列表，将无序的元素插入有序的列表
- 希尔排序 (shell sort) (缩小增量排序) - 较复杂
- 选择排序 (selection)
- 简单选择排序 (selection) - 双重遍历，每次找到最小的元素，最后和该趟遍历的第一个元素进行交换
- 堆排序 (heap sort)
- 归并排序 (merge sort) - 即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。 （递归）
- 二路归并排序
- 多路归并排序
- 交换排序 (swap)
- 非比较类排序
- 计数排序 (counting sort)
- 桶排序 (bucket sort)
- 基数排序 (radix sort)(分配排序)
（五）
- 算法复杂度
| 排序方法 | 时间复杂度（平均） | 时间复杂度（最坏） | 时间复杂度（最好） | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n^2) | O(n^2) | O(n) | O(1) | 稳定 |
| 快速排序 | O(nlog2n) | O(n^2) | O(nlog2n) | O(nlog2n) | 不稳定 |
| 简单插入排序 | O(n^2) | O(n^2) | O(n) | O(1) | 稳定 |
| 希尔排序 | O(n1.3) | O(n^2) | O(n) | O(1) | 不稳定 |
| 简单选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 |
| 堆排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(1) | 不稳定 |
| 归并排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(n) | 稳定 |
| 计数排序 | O(n+k) | O(n+k) | O(n+k) | O(n+k) | 稳定 |
| 桶排序 | O(n+k) | O(n^2) | O(n) | O(n+k) | 稳定 |
| 基数排序 | O(n*k) | O(n*k) | O(n*k) | O(n+k) | 稳定 |
- 相关概念：
1、时间复杂度
- 时间复杂度可以认为是对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
- 常见的时间复杂度有：常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2)
- 时间复杂度O(1)：算法中语句执行次数为一个常数，则时间复杂度为O(1),
2、空间复杂度
- 空间复杂度是指算法在计算机内执行时所需存储空间的度量，它也是问题规模n的函数
- 空间复杂度O(1)：当一个算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1)
- 空间复杂度O(log2N)：当一个算法的空间复杂度与以2为底的n的对数成正比时，可表示为O(log2n)， ax=N，则x=logaN，
- 空间复杂度O(n)：当一个算法的空间复杂度与n成线性比例关系时，可表示为0(n).
复杂度分析
- 常见排序算法分类（排序算法，是算法的基石，你掌握多少？）
- 大O时间复杂度表示法：表示代码执行时间随数据规模增长的变化趋势，又称渐进时间复杂度
- 大O空间复杂度表示法：表示代码执行所占的内存空间随数据规模增长的变化趋势，又称渐进空间复杂度
- 复杂度分析法则
- 单段代码，看循环的次数。
- 多段代码，看代码循环量级。
- 嵌套代码求乘积，比如递归和多重循环。
- 多个规模求加法，方法中并行的两个循环。
- 常用的复杂度级别
- 多项式阶：随着数据规模的增长，算法的执行时间和空间占用，按照多项式的比例增长，包括，O(1)(常数阶)、O(logn)(对数阶)、O(n)(线性阶)、O(nlogn)(线性对数阶)、O(n2)(平方阶)、O(n3)(立方阶)。
- 非多项式阶：随着数据规模的增长，算法的执行时间和空间占用暴增，这列算法性能极差。包括，O(2^n)(指数阶)、O(n!)(阶乘阶)
（六）
- 稳定性
- 假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，A1=A2，且A1在A2之前，而在排序后的序列中，A1仍在A2之前，则称这种排序算法是稳定的；否则称为不稳定的。
- 稳定也可以理解为一切皆在掌握中,元素的位置处在你在控制中.而不稳定算法有时就有点碰运气,随机的成分.当两元素相等时它们的位置在排序后可能仍然相同.但也可能不同.是未可知的.
- 不稳定排序算法
- 快选希堆（快速排序，选择排序，希尔排序，堆排序）
（七）
- 算法总结
- 所需辅助空间最多：归并排序；
所需辅助空间最少：堆排序；
平均速度最快：快速排序；
不稳定：快速排序，希尔排序，堆排序。
冒泡排序
- 1、冒泡排序是一种用时间换空间的排序方法，n小时好
- 2、最坏情况是把顺序的排列变成逆序，或者把逆序的数列变成顺序，最差时间复杂度O(N^2)只是表示其操作次数的数量级
- 3、最好的情况是数据本来就有序，复杂度为O(n)
快速排序
- 1、n大时好，快速排序比较占用内存，内存随n的增大而增大，但却是效率高不稳定的排序算法。
- 2、划分之后一边是一个，一边是n-1个，
这种极端情况的时间复杂度就是O(N^2) - 3、最好的情况是每次都能均匀的划分序列，O(N*log2N)
归并排序
- 1、n大时好，归并比较占用内存，内存随n的增大而增大，但却是效率高且稳定的排序算法。