标签：nlogn 复杂度 C++ ------------ 算法 n2 排序 插入排序
1、排序算法总结
|
时间复杂度 |
空间复杂度 |
稳定性 |
原地排序 |
| 直接插入排序 |
O(n2) |
O(1) |
√ |
√ |
| 折半插入排序 |
O(n2) |
O(1) |
√ |
√ |
| 希尔排序 |
最坏O(n2) |
O(1) |
× |
√ |
| 冒泡排序 |
O(n2) |
O(1) |
√ |
√ |
| 快速排序 |
O(nlogn) |
O(logn) |
× |
√ |
| 简单选择排序 |
O(n2) |
O(1) |
× |
√ |
| 堆排序 |
O(nlogn) |
O(1) |
× |
× |
| 归并排序 |
O(nlogn) |
O(n) |
√ |
× |
| 基数排序 |
O(dn)d是位数 |
O(d) |
√ |
× |
| 桶排序 |
O(n+k)k是桶个数 |
O(n+k) |
√ |
× |
| 时间复杂度和空间复杂度分析： |
|
|
|
|
|
最好时间复杂度 |
最坏时间复杂度 |
平均时间复杂度 |
空间复杂度 |
| ------------ |
------------ |
------------ |
------------ |
------------ |
| 冒泡排序 |
O(n)[初始数组为正序] |
O(12)[初始数组为倒序] |
O(n2) |
O(1) |
| 插入排序 |
O(n)[初始数组为正序] |
O(12)[初始数组为倒序] |
O(n2) |
O(1) |
| 选择排序 |
O(n2) |
O(n2) |
O(n2) |
O(1) |
| 希尔排序 |
O(n) |
O(n2) |
O(n1.3) |
O(1) |
| 快速排序 |
O(nlogn) |
O(logn) |
× |
√ |
| 简单选择排序 |
O(n2) |
O(1) |
× |
√ |
| 堆排序 |
O(nlogn) |
O(1) |
× |
× |
| 归并排序 |
O(nlogn) |
O(n) |
√ |
× |
| 基数排序 |
O(dn)d是位数 |
O(d) |
√ |
× |
| 桶排序 |
O(n+k)k是桶个数 |
O(n+k) |
√ |
× |
标签：nlogn,
复杂度,
C++,
------------,
算法,
n2,
排序,
插入排序
From： https://www.cnblogs.com/xingyuchen/p/17166154.html