常见排序算法详解
我们通常所说的排序算法指的是内部排序算法，即数据记录在内存中进行排序。
排序算法大体可分为两种：
一种是比较排序，时间复杂度 O(nlogn) ~ O(n^2)，主要有：冒泡排序，选择排序，插
入排序，归并排序，堆排序，快速排序等。
另一种是非比较排序，时间复杂度可以达到 O(n)，主要有：计数排序，基数排序，桶排
序等。
下表给出了常见比较排序算法的性能：
排序算法
平均情况
最好情况
最坏情况
辅助空间
稳定性
冒泡排序
O(𝑛
2
)
O(n)
O(𝑛
2
)
O(1)
稳定
简单选择
O(𝑛
2
)
O(𝑛
2
)
O(𝑛
2
)
O(1)
不稳定
直接插入
O(𝑛
2
)
O(n)
O(𝑛
2
)
O(1)
稳定
希尔排序
O(nlogn)~O(𝑛
2
)
O(𝑛
1.3
)
O(𝑛
2
)
O(1)
不稳定
堆排序
O(nlogn)
O(nlogn)
O(nlogn)
O(1)
不稳定
归并排序
O(nlogn)
O(nlogn)
O(nlogn)
O(n)
稳定
快速排序
O(nlogn)
O(nlogn)
O(𝑛
2
)
O(logn)~ O(n)
不稳定
这里有一点我们很容易忽略的是排序算法的稳定性。
排序算法稳定性的简单形式化定义为：如果 Ai = Aj，排序前 Ai 在 Aj 之前，排序后 Ai 还
在 Aj 之前，则称这种排序算法是稳定的。通俗地讲就是保证排序前后两个相等的元素相
对位置不变。
剩余24页未读，继续阅读
资源评论
