首页 > 代码库 > 普林斯顿大学算法课 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/2N^2/2N^2/2最少交换次数
插入排序N^2/2N^2/4N适用于小数组和部分排序的数组
希尔排序 N代码少,复杂度为N^1.5
归并排序 N lgNN lgNN lgN复杂度稳定
快排 N^2/22N lnNN lgN实际应用中速度最快
三路排序 N^2/22N lnNN是普通快排的改进
???N lgNN lgNN lgN上帝算法

 

 

普林斯顿大学算法课 Algorithm Part I Week 3 排序的应用 System Sorts