image

编辑人: 舍溪插画

calendar2025-06-05

message3

visits1131

Java版常用排序算法复杂度

分析&回答

算法复杂度分为时间复杂度和空间复杂度。其作用:

  • 时间复杂度是指执行这个算法所需要的计算工作量;
  • 空间复杂度是指执行这个算法所需要的内存空间;
    时间和空间都是计算机资源的重要体现,而算法的复杂性就是体现在运行该算法时的计算机所需的资源多少;
排序算法英文名称平均时间复杂度最好情况最坏情况空间复杂度排序方式稳定性
冒泡排序BubbleO(n²)O(n)O(n²)O(1)In-place稳定
选择排序SelectionO(n²)O(n²)O(n²)O(1)In-place不稳定
插入排序InsertionO(n²)O(n)O(n²)O(1)In-place稳定
希尔排序ShellO(n ㏒n)O(n ㏒²n)O(n ㏒²n)O(1)In-place不稳定
归并排序MergeO(n ㏒n)O(n ㏒n)O(n ㏒n)O(n)Out-place稳定
快速排序QuickO(n ㏒n)O(n ㏒n)O(n²)O(㏒n)In-place不稳定
堆排序HeapO(n ㏒n)O(n ㏒n)O(n ㏒n)O(1)In-place不稳定
计数排序CountingO(n + k)O(n + k)O(n + k)O(k)Out-place稳定
桶排序BucketO(n + k)O(n + k)O(n²)O(n + k)Out-place稳定
基数排序RadixO(n × k)O(n × k)O(n × k)O(n + k)Out-place稳定

反思&扩展

特别关注快速排序归并排序

O(x)是啥意思?

简单直观的 O(1) 、 O(n) 、O(log n) 复杂度说起

  • O(1) 表示一次操作即可直接取得目标元素(比如字典或哈希表),
  • O(n) 意味着先要检查 n 个元素来搜索目标
  • O(log n) 时间复杂度可能是在学二分搜索算法

image-1691386057394


喵呜刷题:让学习像火箭一样快速,快来微信扫码,体验免费刷题服务,开启你的学习加速器!

创作类型:
原创

本文链接:Java版常用排序算法复杂度

版权声明:本站点所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。
分享文章
share