首页 > 代码库 > 各种查找排序算法比较
各种查找排序算法比较
| 算法 | 平均时间 | 最差时间 | 最好时间 | 稳定度 | 空间 | 备注 | 思想 |
| 插入 | O(n2) | O(n2) | O(n) | 稳定 | O(1) | 大部分已排序时较好 | |
| 希尔 | O(nlogn) | O(ns)[s属于(1,2)] | O(n) | 不稳定 | O(1) | s是所选分组 | |
| 冒泡 | O(n2) | O(n2) | O(n) | 稳定 | O(1) | n小时较好 | |
| 快速 | O(nlogn) | O(n2) | O(nlogn) | 不稳定 | O(nlogn) | n大时较好 | 分治法 |
| 交换 | O(n2) | O(n2) | O(n) | 不稳定 | O(1) | n小时较好 | |
| 选择 | O(n2) | O(n2) | O(n2) | 不稳定 | O(1) | n小时较好 | |
| 堆 | O(nlogn) | O(nlogn) | O(nlogn) | 不稳定 | O(1) | n大时较好 | |
| 归并 | O(nlogn) | O(nlogn)) | O(nlogn)) | 稳定 | O(n) | n大时较好 | 分治法 |
| 基数 | O(d(r+n)) | O(d(r+n)) | O(d(r+nd)) | 稳定 | O(n) | B是真数(0-9)，R是基数(个十百) | |
| 傅里叶变换 | 分治法 | ||||||
| 最长公共子序列 | 动态规划 | ||||||
| 克鲁斯卡尔 | O（eloge） | 最小生成树，e为边数目 | 贪心法 | ||||
| 普里姆 | O（n2） | 最小生成树 | 贪心法 | ||||
| 迪杰斯特拉 | O(n2) | 点的最短路径 | 动态规划 | ||||
| 佛洛依德 | O(n3) | 点对的最短路径 | 动态规划 | ||||
| 拓扑排序 | O（n+e） | ||||||
| 关键路径 | O（n+e） | ||||||
| 辗转相除法 | O（logn） | 最大公约数，gcd(a,b)= gcd(b,a mod b) |
转自Cblog->java成长之路
各种查找排序算法比较
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。