各种排序算法的时间复杂度,排序算法与时间复杂度

文章目录算法效率度量时间复杂度master公式常用排序算法及其时间复杂度冒泡排序(bubblesort)：$O(N^{2})$选择排序：$O(N^{2})$插入排序：$O(N^{2})$归并排序：$O(Nlog{N})$总结

算法效率度量

1.时间复杂度O(n)
原则：

常数1代替所有加法中的常数只保留最高阶数项(且不要前面的系数)O(1)<O(log n)<O(n)<O(n logn)<O(n^2)

2.空间复杂度
常用空间换时间

时间复杂度

时间复杂度：算法性能指标（本质常数时间操作的个数）；先看指标再看系数；先看高阶项再看低阶项
常数时间操作：例如位操作、算术运算等。

master公式

T ( N ) = a T ( N / b ) + O ( N d ) T(N)=aT(N/b)+O(N^{d}) T(N)=aT(N/b)+O(Nd)
其中a表示子过程发生次数，b表示子过程样本量，
l o g b a > d → log^{a}_{b}>d rightarrow logba>d→复杂度为 O ( N l o g b a ) O(N^{log^{a}_{b}}) O(Nlogba)
l o g b a = d → log^{a}_{b}=d rightarrow logba=d→复杂度为 O ( N d l o g N ) O(N^{dlog^{N}}) O(NdlogN)
l o g b a > d → log^{a}_{b}>d rightarrow logba>d→复杂度为 O ( N d ) O(N^{d}) O(Nd)

常用排序算法及其时间复杂度冒泡排序(bubblesort)： O ( N 2 ) O(N^{2}) O(N2) 选择排序： O ( N 2 ) O(N^{2}) O(N2) 插入排序： O ( N 2 ) O(N^{2}) O(N2)

时间复杂度与数据状况有关，最好 O ( N ) O(N) O(N)最差 O ( N 2 ) O(N^{2}) O(N2)。但算法性能一律按最差考虑，即插入排序时间复杂度为 O ( N 2 ) O(N^{2}) O(N2)

归并排序： O ( N l o g N ) O(Nlog{N}) O(NlogN)

分治思想

总结常用排序算法时间复杂度空间复杂度稳定性平均情况最好情况最坏情况辅助存储交换排序冒泡排序 O(n*n) O(n) O(n*n) O(1) 稳定快速排序 O(n*logn) O(n*logn) O(n*n) O(n*logn) 不稳定插入排序直接插入 O(n*n) O(n) O(n*n) O(1) 稳定shell排序 O(n*n) O(n) O(n*n) O(1) 不稳定选择排序直接选择 O(n*n) O(n*n) O(n*n) O(1) 不稳定堆排序 O(n*logn) O(n*logn) O(n*logn) O(1) 不稳定归并排序 O(n*logn) O(n*logn) O(n*logn) O(n) 稳定