常用排序算法的时间复杂度和空间复杂度及稳定性
一、时间复杂度
二、空间复杂度
冒泡排序,简单选择排序,堆排序,直接插入排序,希尔排序的空间复杂度为O(1),因为需要一个临时变量来交换元素位置,(另外遍历序列时自然少不了用一个变量来做索引)
快速排序空间复杂度为O(logn)~O(n)(就空间复杂度来说，主要是递归造成的栈空间的使用，最好情况，递归树的深度为logn，其空间复杂度也就为O(logn)，最坏情况，需要进行n‐1递归调用，其空间复杂度为O(n)，平均情况，空间复杂度也为O(logn)) ,归并排序空间复杂是O(n),需要一个大小为n的临时数组.
桶排序、计数排序、基数排序的空间复杂度是O(m),m为所使用桶的数量。
三、稳定性
稳定的排序算法：
冒泡排序、插入排序、归并排序、计数排序、基数排序、桶排序
不稳定的排序算法：
快速排序、选择排序、堆排序、希尔排序
四、不受初始元素影响的效率的排序
选择排序、堆排序、归并排序
五、内部排序和外部排序
内部排序：在内存中进行排序
外部排序：因排序的数据量很大，一次不能容纳全部的数据，在排序的过程中需要访问外存。