第1个回答 2012-12-09
常用的排序算法有插入排序，希尔排序，冒泡排序，快速排序，归并排序，堆排序还有基数排序。
排序算法一般考虑的就是两个方面，即时间复杂度和空间复杂度。
其中插入排序，冒泡排序是简单排序，排序的平均时间复杂度是O（n^2）, 最坏的情况是O(n^2)，辅助存储空间是O(1)。
快速排序的平均时间复杂度是O(nlogn), 最坏的情况是O(n^2), 辅助存储空间是O(logn)
归并排序的平均时间复杂度是O(nlogn), 最坏的情况是O(nlogn), 辅助存储空间是O(n)
堆排序平均时间复杂度是O(nlogn), 最坏的情况是O(nlogn), 辅助存储空间是O(1)
基数排序平均时间复杂度是O(d(n+rd)), 最坏的情况是O(d(n+rd)), 辅助存储空间是O(rd),其中d关键字的个数，rd是关键字的取值的个数。
从平均性能上来而言，快速排序最佳，其所需的时间最省，但快排在最坏的情况下的时间性能不如堆排序和归并排序。而后者相比的结果是，在n较大的时候，归并排序需要的时间比堆排序省，但它需要的辅助存储空间比较多。
从方法的稳定性来比较，基数排序是稳定的内排序，所有时间复杂度为O（n^2）的简单排序都是稳定的。然而，快速排序，归并排序，堆排序等时间性能较好的排序方法都是不稳定的。
具体每个排序的思想，楼主可以百度一下，百度百科都有相应的词条。