排序的应用

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

典型的应用有

• 对名称进行排序
  

• 排序MP3音乐文件

• 显示Google的搜索结果

• 按标题顺序列出RSS订阅

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

• 找出中位数

• 数据库中的二分查找

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

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

不是特别典型的应用有

• 数据压缩

• 计算机图形

• 计算生物

• 负载平衡

编程语言中的排序算法

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

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

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

• 使用三路分区

• 分区依据

  • 小的数组使用中间的值

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

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

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

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

排序算法种类

内部排序

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

快速排序、归并排序、堆排序、希尔排序、采样排序（samplesort）

纸牌排序、红黑排序、张开排序、Yaroslavskiy排序、p排序

外部排序

多相归并排序、层叠归并、振荡排序

字符串排序

分布排序、MSD、LSD、三路快排

并行排序

Bitonic排序、Batcher奇偶排序

平滑排序、立方排序、列排序

GPU排序

选择哪种算法呢

选择哪种算法最终还是要看需求。