昨天做腾讯的笔试题中有一道选择题，问几种排序的最坏情况，快排，冒泡大家肯定都知道是n^2,当时选项中有一个堆排序，不是很确定，下来就把这些收集了一下
表格转自http://www.cnblogs.com/xiaochun126/p/5086037.html
之后就重点说一下堆排序和快排的选择问题
各种常用排序算法
类别
排序方法
时间复杂度
空间复杂度
稳定性
复杂性
特点
最好
平均
最坏
辅助存储
简单
插入
排序
直接插入
O(N)
O(N2)
O(N2)
O(1)
稳定
简单
希尔排序
O(N)
O(N1.3)
O(N2)
O(1)
不稳定
复杂
选择
排序
直接选择
O(N)
O(N2)
O(N2)
O(1)
不稳定
堆排序
O(N*log2N)
O(N*log2N)
O(N*log2N)
O(1)
不稳定
复杂
交换
排序
冒泡排序
O(N)
O(N2)
O(N2)
O(1)
稳定
简单
1、冒泡排序是一种用时间换空间的排序方法，n小时好 2、最坏情况是把顺序的排列变成逆序，或者把逆序的数列变成顺序，最差时间复杂度O(N^2)只是表示其操作次数的数量级 3、最好的情况是数据本来就有序，复杂度为O(n)
快速排序
O(N*log2N)
O(N*log2N)
O(N2)
O(log2n)~O(n)
不稳定
复杂
1、n大时好，快速排序比较占用内存，内存随n的增大而增大，但却是效率高不稳定的排序算法。 2、划分之后一边是一个，一边是n-1个， 这种极端情况的时间复杂度就是O(N^2) 3、最好的情况是每次都能均匀的划分序列，O(N*log2N)
归并排序
O(N*log2N)
O(N*log2N)
O(N*log2N)
O(n)
稳定
复杂
1、n大时好，归并比较占用内存，内存随n的增大而增大，但却是效率高且稳定的排序算法。
基数排序
O(d(r+n))
O(d(r+n))
O(d(r+n))
O(rd+n)
稳定
复杂
注：r代表关键字基数，d代表长度，n代表关键字个数
大家可以看到，堆排序的时间复杂度是很稳定的，而快排的时间复杂度最坏情况下会到n^2,那么为什么不都用堆排序呢？
首先，时间复杂度这个概念只是一个粗略的估计概念，在真实情况下， 一般快排的效率比堆排序高很多。
快排：数组中交换数据，在数据量不是特别大，而且离散程度较高的情况下效率很高
堆排序：创建堆，数据交换，调整堆的时间均很多
所以在实际应用中，我们用快排会更多一点。
堆排序的典型应用：在100万个数字中找出最大的100个这种问题，构建一个小顶堆然后遍历调整就可以了
为什么是小顶堆：小顶堆，最小的数就在最上面，只要与最上面的数进行比较就可以了，所以是小顶
