经典排序算法

一、通过插入进行排序
1.插入排序
    原理是通过元素找位置，实现简单，时间复杂度为O(n^2),空间复杂度为O(1)
2.希尔排序
    基于插入排序实现，根据TAOCP，当n<1000时选择间隔序列1,4,13,40,121,367性能比较好，时间复杂度接近O(n*lgn),空间复杂度为O(1)

二、通过交换进行排序
3.冒泡排序
    实现简单，时间复杂度为O(n^2),空间复杂度为O(1),经验表面它是这些算法中性能最差的
4.快速排序
    名副其实，性能好，时间复杂度为O(n*lgn),空间复杂度为O(1)，但是在输入的所有元素很多相等或者递增排列时其时间复杂度变为O(n^2)，它使用递归

三、通过选择进行排序
5.选择排序
    原理是通过位置找元素，实现简单，时间复杂度为O(n^2),空间复杂度为O(1)
6.堆排序
    实现复杂，通过最大堆实现递增排序，时间复杂度为O(n*lgn),空间复杂度为O(1)

四、通过合并进行排序
7.合并排序
    原理是合并两个已经排序的数组比直接对一个大数组排序简单，时间复杂度为O(n*lgn),空间复杂度为O(n)，性能稳定，但需要使用大量的元素复制，通过优化代码可使空间复杂度降低至O(n)，它使用递归

五、其他排序方法
8.分布计数排序
    只适合于小范围内的整数排序，性能相当好，其他方法没法比