数据结构之内部排序性能比较

内部排序方法	最优复杂度	最坏复杂度	平均复杂度	空间复杂度	稳定性
插入排序	O(n)	O( n2 )	O( n2 )	O(1)	稳定
折半插入	O(n)	O( n2 )	O( n2 )	O(1)	稳定
希尔排序			O(n^1.5)	O(1)	不稳定
冒泡排序	O(n)	O( n2 )	O( n2 )	O(1)	稳定
快速排序	O( nlog2n )	O( n2 )	O( nlog2n )	O( log2n )	不稳定
选择排序	O( n2 )	O( n2 )	O( n2 )	O(1)	不稳定
堆排序	O( nlog2n )	O( nlog2n )	O( nlog2n )	O(1)	不稳定
归并排序	O( nlog2n )	O( nlog2n )	O( nlog2n )	O(n)	稳定
基数排序	O(d(r+n))	O(d(r+n))	O(d(r+n))	O(r+n)	稳定

---