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

时间:2022-03-12 00:06:14

排序算法有着广泛的应用

典型的应用:

  • 排序名称
  • 排序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 上帝算法