1 八大排序的复杂度和稳定性

排序	平均情况	最好情况	最坏情况	辅助空间	稳定性
冒泡排序	O(n^2)	O(n)	O(n^2)	O(1)	稳定
选择排序	O(n^2)	O(n^2)	O(n^2)	O(1)	不稳定
插入排序	O(n^2)	O(n)	O(n^2)	O(1)	稳定
希尔排序	O(n^1.3)	O(n logn)	O(n^2)	O(1)	不稳定
快速排序	O(n logn)	O(n logn)	O(n^2)	O(n logn)	不稳定
归并排序	O(n logn)	O(n logn)	O(n logn)	O(n)	稳定
堆排序	O(n logn)	O(n logn)	O(n logn)	O(1)	不稳定
基数排序	O(d(n+r))	O(d(n+r))	O(d(n+rd))	O(n+rd)	稳定

稳定性

如果一个排序，能够使得值相同的元素在排序后相对位置关系不变，则称该排序稳定，否则不稳定。