十大经典排序算法
https://www.cnblogs.com/onepixel/p/7674659.html
快速排序代码示例
https://shimo.im/docs/98KjvGwwGpTpYGKy/
归并排序代码示例
https://shimo.im/docs/YqgG6vtdKwkXJkWx/
堆排序代码示例
https://shimo.im/docs/6kRVHRphpgjHgCtx/
| 排序方法 | 时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 插入排序 | O(n^2) | O(n^2) | O(n) | O(1) | 稳定 |
| 希尔排序 | O(n^1.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(n^2) | O(n^2) | O(n) | O(1) | 稳定 |
| 快速排序 | O(nlog2n) | O(n^2) | O(nlog2n) | O(nlog2n) | 不稳定 |
| 归并排序 | 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) | 稳定 |
log2n 的排序方法需要重点掌握
快速，归并排序用到了分治的思想。
每次找最小值,然后放到待排序数组的起始位置。
从前到后逐步构建有序序列;对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
嵌套循环，每次查看相邻元素，如果逆序，则交换。每次冒泡，最大的元素都会被挪到后面，其实和选择排序是相逆的。
….