【数据结构(六)】排序算法的时间复杂度比较（4）

2023-12-06 09:20:03
开发
51

文章目录

常用排序算法对比

常用排序算法对比

排序法	平均时间复杂度	最好情况	最差情况	空间复杂度	排序方式	稳定度
冒泡排序	$O(n^2)$	$O (n)$	$O(n^2)$	$O (1)$	In-place	稳定
选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O (1)$	In-place	不稳定
插入排序	$O(n^2)$	$O (n)$	$O(n^2)$	$O (1)$	In-place	稳定
希尔排序	$O (n l o g n)$	$O(nlog^2n)$	$O(nlog^2n)$	$O (1)$	In-place	不稳定
归并排序	$O (n l o g n)$	$O (n l o g n)$	$O (n l o g n)$	$O (n)$	Out-place	稳定
快速排序	$O (n l o g n)$	$O (n l o g n)$	$O(n^2)$	$O (l o g n)$	In-place	不稳定
堆排序	$O (n l o g n)$	$O (n l o g n)$	$O (n l o g n)$	$O (1)$	In-place	不稳定
计数排序	$O (n + k)$	$O (n + k)$	$O (n + k)$	$O (k)$	Out-place	稳定
桶排序	$O (n + k)$	$O (n + k)$	$O(n^2)$	$O (n + k)$	Out-place	稳定
基数排序	$O (n \times k)$	$O (n \times k)$	$O (n \times k)$	$O (n + k)$	Out-place	稳定

相关术语解释：
① 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
② 不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；
③ 内排序：所有排序操作都在内存中完成；
④ 外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
⑤ 时间复杂度：一个算法执行所耗费的时间。
⑥ 空间复杂度：运行完一个程序所需内存的大小。
⑦ n：数据规模
⑧ k：“桶”的个数
⑨ In-place：不占用额外内存
⑩ Out-place：占用额外内存

原文地址:https://blog.csdn.net/weixin_44883789/article/details/134809650 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1732208246036500480.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部

【数据结构(六)】排序算法的时间复杂度比较（4）

文章目录

常用排序算法对比

相关推荐

最近更新

热门阅读