1.插入排序法

直接插入排序，希尔排序，不常用的：Tree sort；Library sort：Patience sorting

2.互换排序

冒泡排序，快速排序，不常用的：鸡尾酒排序，奇偶排序

3.选择排序

直接选择排序，堆排序

4.归并排序

归并排序

二、不基于斗劲的排序算法

基数排序，桶排序

三、空间，时候错杂度，稳定性

        

1.O（n^2）机能解析

均匀机能为O（n^2）的有：直接插入排序，选择排序，冒泡排序

在数据范围较小时（9W内），直接插入排序，选择排序差不久不多。当数据较大时，冒泡排序算法的时候价格高。机能为O（n^2）的算法根蒂根基上是相邻元素进行斗劲，根蒂根基上都是稳定的。

2.O（nlogn）机能解析

均匀机能为O（nlogn）的有：快速排序，归并排序，希尔排序，堆排序。此中，快排是好的， 其次是归并和希尔，堆排序在数据量很大时结果明显。

这四种排序可看作为“进步前辈算法”，此中，快排效力高，但在待排序列根蒂根基有序的景象下，会变成冒泡排序，接近O（n^2）.

希尔排序对增量的标准没有较为合意的答案，增量对机能会有影响。

归并排序效力很是不错，在数据范围较大的景象下，比希尔排序和堆排序要好。

多半进步前辈的算法都是因为跳跃式的斗劲，降落了斗劲次数，但就义了排序的稳定性。

3. 插入排序，冒泡排序，二叉树排序，归并排序都是稳定的

 选择排序，希尔排序，快速排序，堆排序是不稳定的。

四、排序算法选择

1.数据范围较小

  （1）待排序列根蒂根基序的景象下，可以选择直接插入排序；

  （2）对稳定性不作请求宜用选择排序，对稳定性有请求宜用插入或冒泡

2.数据范围不是很大

（1）完全可以用内存空间，序列混乱无序，对稳定性没有请求，快速排序，此时要付出log（N）的额外空间。

 （2）序列本身可能有序，对稳定性有请求，空间容许下，宜用归并排序

3.海量级此外数据，必须按块放在外存上

   （1）对稳定性有求，则可推敲归并排序。

    （2）对稳定性没请求，宜用堆排序

4.序列初始根蒂根基有序（正序），宜用直接插入，冒泡，随机快排

五、各排序算法整体解析

  冒泡排序、插入排序、希尔排序以及快速排序对数据的有序性斗劲敏感，尤其是冒泡排序和插入排序；

 选择排序不关怀表的初始次序，它的最坏景象的排序时候与其景象没几许差别，其斗劲次数为 n（n-1）/2，但选择排序可以   很是有效的移动元素。是以对次序近乎正确的表，选择排序可能比插入排序慢很多。

冒泡排序在优景象下只须要经过n-1次斗劲即可得出成果（即对于完全正序的表），最坏景象下也要进行n（n-1）/2 次斗劲，与选择排序的斗劲次数雷同，但数据互换的次数要多余选择排序，因为选择排序的数据互换次数顶多为 n-1，而冒泡排序最坏景象下的数据互换n（n-1）/2 。冒泡排序不必然要进行 趟，但因为它的记录移动次数较多，所以它的均匀时候机能比插入排序要差一些。

插入排序在好的景象下有起码的斗劲次数 ，然则它在元素移动方面效力很是低下，因为它只与邻接的元素进行斗劲，效力斗劲低。

希尔排序实际上是预处理惩罚阶段优化后的插入排序，一般而言，在 斗劲大时，希尔排序要明显优于插入排序。

快速排序采取的“大事化小，小事化了”的思惟，用递归的办法，将原题目分化成若干范围较小但与原题目类似的子题目进行求解。快速算法的均匀时候错杂度为O（nlogn） ，均匀而言，快速排序是基于关键字斗劲的内部排序算法中速度快者；然则因为快速排序采取的是递归的办法，是以当序列的长度斗劲大时，对体系栈占用会斗劲多。快速算法尤其实用于随机序列的排序。

是以，均匀而言，对于一般的随机序列次序表而言，上述几种排序算法机能从低到高的次序大致为：冒泡排序、插入排序、选择排序、希尔排序、快速排序。但这个好坏次序不是绝对的，在不合的景象下，甚至可能呈现完全的机能逆转。

对于序列初始状况根蒂根基有正序，可选择对有序性较敏感的如插入排序、冒泡排序、选择排序等办法

对于序列长度 斗劲大的随机序列，应选择均匀时候错杂度较小的快速排序办法。

各类排序算法都有各自的优毛病，适应于不合的应用景象，是以在选择一种排序算法解决实际题目之前，该当先解析实际题目的类型，再连络各算法的特点，选择一种合适的算法

参考材料:

　http://gengning938.blog.163.com/blog/static/128225381201141121326346/

　http://blog.csdn.net/without0815/article/details/7697916