Comments (1)
Snailclimb
commented on June 1, 2024
O(n^2)
好的，顺便重新整理了一个表格：
| 排序算法 | 时间复杂度（平均） | 时间复杂度（最差） | 时间复杂度（最好） | 空间复杂度 | 排序方式 | 稳定性 |
|---|---|---|---|---|---|---|
| 冒泡排序 | O(n^2) | O(n^2) | O(n) | O(1) | 内部排序 | 稳定 |
| 选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 内部排序 | 不稳定 |
| 插入排序 | O(n^2) | O(n^2) | O(n) | O(1) | 内部排序 | 稳定 |
| 希尔排序 | O(nlogn) | O(n^2) | O(nlogn) | O(1) | 内部排序 | 不稳定 |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 外部排序 | 稳定 |
| 快速排序 | O(nlogn) | O(n^2) | O(nlogn) | O(logn) | 内部排序 | 不稳定 |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 内部排序 | 不稳定 |
| 计数排序 | O(n+k) | O(n+k) | O(n+k) | O(k) | 外部排序 | 稳定 |
| 桶排序 | O(n+k) | O(n^2) | O(n+k) | O(n+k) | 外部排序 | 稳定 |
| 基数排序 | O(n×k) | O(n×k) | O(n×k) | O(n+k) | 外部排序 | 稳定 |
术语解释：
- n：数据规模，表示待排序的数据量大小。
- k：“桶” 的个数，在某些特定的排序算法中（如基数排序、桶排序等），表示分割成的独立的排序区间或类别的数量。
- 内部排序：所有排序操作都在内存中完成，不需要额外的磁盘或其他存储设备的辅助。这适用于数据量小到足以完全加载到内存中的情况。
- 外部排序：当数据量过大，不可能全部加载到内存中时使用。外部排序通常涉及到数据的分区处理，部分数据被暂时存储在外部磁盘等存储设备上。
-
稳定：如果 A 原本在 B 前面，而
$A=B$ ，排序之后 A 仍然在 B 的前面。 -
不稳定：如果 A 原本在 B 的前面，而
$A=B$ ，排序之后 A 可能会出现在 B 的后面。 - 时间复杂度：定性描述一个算法执行所耗费的时间。
- 空间复杂度：定性描述一个算法执行所需内存的大小。
from javaguide.
Related Issues (20)
- 「Java内存区域详解（重点）」 文档的「方法区」部分描述好像有误 HOT 1
- LinkedHashMap实现LRU部分勘误
- 关于聚簇索引和非聚簇索引的定义 HOT 1
- 关于Mysql三大日志详解--undo-log描述不够具体 HOT 2
- Java集合概览部分多写了一个map HOT 1
- Firefox移动端页面返回到顶部按钮不会跟随页面阅读多少变化 HOT 1
- 死信队列这里的介绍语句 HOT 2
- 索引下推里例子的月份写错了 HOT 2
- Mongodb使用b+树，为什么放一篇b树的论证链接？ HOT 1
- Java NIO 核心知识总结文章-个别图片背景是透明的，导致深色模式看不清字 HOT 1
- 构造方法用synchronized关键词修饰解释有误 HOT 1
- 关于线程等待和阻塞两种状态 HOT 1
- 双亲委派模型举例不严谨 HOT 1
- SQL语句中having的执行顺序是在select之前吧 HOT 2
- jdk1.7起，静态变量是位于堆区，而不是方法区
- SPI机制的设计思路和使用场景没有讲到核心
- 网站已经很久没有从此仓库更新 HOT 2
- HashMap 和 Hashtable 的区别补充
- 不推荐使用外键与级联原因的理解（对作者看法的其他意见） HOT 2
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from javaguide.