算法基础知识
Big O
时间：随着数据规模的增加，需要进行的时长变化规律
- 不考虑必须要做的操作：循环、赋初值、程序初始化
- 不考虑常数项：2n -> n
- 不考虑低次项：n^2 + n -> n^2
空间：随着数据规模增加，需要额外开辟的空间
- 遍历使用的临时变量不计算
排序算法
| 中文名称 | 英文名称 | 平均时间复杂度 | 最坏时间复杂度 | 最好时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|---|
| 选择排序 | Selection | n^2 | n^2 | n^2 | 1 | 不稳定 |
| 冒泡排序 | Bubble | n^2 | n^2 | n | 1 | 稳定 |
| 插入排序 | Insertion | n^2 | n^2 | n | 1 | 稳定 |
| 快速排序 | Quick | nlog(2, n) | n^2 | nlog(2, n) | log(2, n) | 不稳定 |
| 归并排序 | Merge | nlog(2, n) | nlog(2, n) | nlog(2, n) | n | 稳定 |
| 堆排序 | Heap | nlog(2, n) | nlog(2, n) | nlog(2, n) | 1 | 不稳定 |
| 希尔排序 | Shell | n^1.3 | n^2 | n | 1 | 不稳定 |
| 桶排序 | Bucket | n + k | n^2 | n | n + k | 稳定 |
| 计数排序 | Counting | n + k | n + k | n + k | n + k | 稳定 |
| 基数排序 | Radix | n * k | n * k | n * k | n + k | 稳定 |
不稳定：相同的值经过排序后相对位置可能会发送变化
口诀：选泡插，快归堆希桶计基，恩方老恩恩一三，对恩加k恩乘k，不稳稳稳不稳稳，不稳不稳稳稳稳。
选择排序
原理：从第一个数开始，往后遍历，找到最小的数，记录最小值的位置，将该值和第一个位置的值进行交换
冒泡排序
原理：从第一个数开始，往后遍历，如果遍历的数比后一个位置的数大，则俩数交换位置，使最大的数到之后位置
冒泡排序是从后往前遍历
插入排序
原理：从第二个数开始，往前遍历，如果遍历的数比前一个位置的数小，则将该数与前一个数位置交换
快速排序
归并排序
堆排序
希尔排序
原理：希尔排序是基于插入排序的一种排序方法，先将数组分成若干个子数组，每个子数组再进行插入排序