排序算法种类及应用场景：

插入排序　　很少的元素或几乎有序的元素

堆排序　　　关注最坏情况

快速排序　　希望能够得到一个好的平均情况下性能

桶排序　　　元素是从一个密集集合中抽取出

 

插入排序

它的原理其实很简单。你一定有这样的经历，你在摸牌的时候，你一定是边摸牌边理排。那么你是怎么理的呢？我是按顺序来的，摸到一张，就插到相应的位置中。这里的插入法就是这个原理。

 

堆排序

堆排序主要是将数组看成二叉树，通过二叉树的比较，每次将最大的排到最前面，然后将最大的排到最后，这样的话最大的已经排好。然后剩下的再进行递归，最后能得到有序的数据。

 

快速排序

我把它理解为中值排序的升级版，主要是中值排序是需要左右长度相等，而在快速排序中，对于左右两个数组要求没有那么高。

 

中值排序

将需要排序的数组左右等分，要求左边的值始终比最中间的值要小，右边的值始终比最中间的值要大，然后递归。

 

计数排序

用于数组很长，设为n，但是数值只有那么几个，设为m，若m<<n，那么可以用计数排序，它的复杂度为O(n)。

它先是创建一个长度为m的数组，然后进行两次遍历，在第一次遍历中，计算数值出现的次数；然后第二次是遍历新建的那个数组，利用计数值，将原来的数组重写。

 

选择排序

这是在我一开始学习c语言的时候，经常会使用的一个排序例子。不过它在这些算法中效率应该是最低的。

 

在erlang中，它对于快速排序只需要很少的语句就可以实现：

qsort([ ]) -> [ ];qsort([ Pivot | T ]) ->    qsort([ X || X<- Pivot, X < Pivot ])    ++ Pivot    ++ qsort([ X || X <- Pivot, X >= Pivot ]).