基于比较排序算法时间下限为O(nlogn)，计数排序时间复杂度O(n)。

　　在待排序列基本有序的情况下，直接插入排序是最佳排序算法；快速排序的效率一般情况下都比较高，但在待排序列基本有序的情况下，时间复杂度接近 O(n2)；归并排序效率仅次于快速排序，是稳定排序，经常用于多个有序的数据文件归并成一个有序的数据文件以及求解逆序对数，最好、最坏、平均时间复杂度均为O(nlogn)，空间复杂度为O(n)；桶排序在数据分布均匀且分区粒度够精细的情况下，其时间复杂度接近于O(n)，但空间复杂度将非常大。

 

一. 选择排序

　　选择排序(包括堆排序，Heapsort)是不稳定，以一次索引交换代替三次值交换。选择排序的交换操作介于 0 和 (n - 1） 次之间，比较操作为n (n - 1) / 2 次之间，赋值操作介于 0 和 3 (n - 1） 次之间。