首页 > 代码库 > 普林斯顿公开课 算法3-4:快排的应用

普林斯顿公开课 算法3-4:快排的应用

排序的应用


排序算法有着广泛的应用。


典型的应用有

  • 对名称进行排序

  • 排序MP3音乐文件

  • 显示Google的搜索结果

  • 按标题顺序列出RSS订阅


排序之后下列问题就变得非常简单了

  • 找出中位数

  • 数据库中的二分查找

  • 找出统计数据中的异常值

  • 在邮箱中找出重复的邮件


不是特别典型的应用有

  • 数据压缩

  • 计算机图形

  • 计算生物

  • 负载平衡


编程语言中的排序算法


java中对于基本类型使用快排,对于引用类型使用归并排序。因为归并排序很稳定,而且保证复杂度为NlgN


Java、C/C++中的快排都有以下特性:

  • 对于小的子数组,使用插入排序

  • 使用三路分区

  • 分区依据

    • 小的数组使用中间的值

    • 中等数组使用3个数的中位数

    • 大的数组使用9个数的中位数


取9个数的中位数有个好处就是不需要在排序之前洗牌。


Java中的快排有个致命的缺陷,当输入实现精心编制的数组时,java的排序算法就产生堆栈溢出的错误,C语言中的qsort也是一样。


排序算法种类


内部排序

插入排序、选择排序、冒泡排序、筛动排序

快速排序、归并排序、堆排序、希尔排序、采样排序(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上帝算法