首页 > 代码库 > 普林斯顿大学算法课 Algorithm Part I Week 3 排序的应用 System Sorts
普林斯顿大学算法课 Algorithm Part I Week 3 排序的应用 System Sorts
排序算法有着广泛的应用
典型的应用:
- 排序名称
- 排序MP3音乐文件
- 显示Google的网页排名的搜索结果
- 按标题顺序列出RSS订阅
排序之后下列问题就变得非常简单了
- 找出中位数(median)
- 找出统计数据中的异常值
- 数据库中的二分查找
- 在邮箱中找出重复的邮件
不是特别典型的应用:
- 数据压缩
- 计算机图形
- 计算生物
- 负载平衡
Java系统排序(System sorts)
Arrays.sort().
- 有不同的方法对应不同的基本类型
- 有一个实现Comparable接口的方法
- 有一个使用Comparator的方法
- 对基本类型使用经过优化的快排;对对象使用经过优化的归并排序
Java的系统排序不是完全可靠的
排序算法种类:
内部排序:
插入排序、选择排序、冒泡排序、筛动排序
快速排序、归并排序、堆排序、希尔排序、采样排序(samplesort)
纸牌排序、红黑排序、张开排序、Yaroslavskiy排序、p排序
外部排序:
多相归并排序、层叠归并、振荡排序
字符串排序:
分布排序、MSD、LSD、三路快排
并行排序::
Bitonic排序、Batcher奇偶排序
平滑排序、立方排序、列排序
GPU排序
应该选择哪一种算法?
应该根据需求选择算法。
原地排序 | 稳定性 | 最坏 | 平均 | 最好 | 备注 | |
选择排序 | 是 | N^2/2 | N^2/2 | N^2/2 | 最少交换次数 | |
插入排序 | 是 | 是 | N^2/2 | N^2/4 | N | 适用于小数组和部分排序的数组 |
希尔排序 | 是 | ? | ? | N | 代码少,复杂度为N^1.5 | |
归并排序 | 是 | N lgN | N lgN | N lgN | 复杂度稳定 | |
快排 | 是 | N^2/2 | 2N lnN | N lgN | 实际应用中速度最快 | |
三路排序 | 是 | N^2/2 | 2N lnN | N | 是普通快排的改进 | |
??? | 是 | 是 | N lgN | N lgN | N lgN | 上帝算法 |
普林斯顿大学算法课 Algorithm Part I Week 3 排序的应用 System Sorts
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。