Tag Archives: sort

Sort Index

插入类排序:

插入排序       最好O(n)   最坏O(n^2)   空间O(1)
*希尔排序     最好O(n^1.3)   最坏O(n^2)   空间O(1)

选择类排序:

*选择排序    最好O(n^2)   最坏O(n^2)   空间O(1)
*堆排序        最好O(nlogn)   最坏O(nlogn)   空间O(1)

交换类排序:

冒泡排序     最好O(n)   最坏O(n^2)   空间O(1)
*快速排序     最好O(nlogn)   最坏O(n^2)   空间O(logn)~O(n)

归并类排序:

归并排序     最好O(nlogn)   最坏O(nlogn)   空间O(n)

非基于比较的排序:

基数排序
桶排序
计数排序

带*号为不稳定排序
从最好情况看,冒泡和直接插入排序更好;
从最坏情况看,堆排序和归并又强过快速排序和其他简单排序;
从稳定性看,归并排序好;
从空间看,堆排序O(1),若对内存使用量在乎,归并和快排就不太好。