基于比較排序算法時間下限為O(nlogn)，計數(shù)排序時間復(fù)雜度O(n)。

　　在待排序列基本有序的情況下，直接插入排序是最佳排序算法；快速排序的效率一般情況下都比較高，但在待排序列基本有序的情況下，時間復(fù)雜度接近 O(n2)；歸并排序效率僅次于快速排序，是穩(wěn)定排序，經(jīng)常用于多個有序的數(shù)據(jù)文件歸并成一個有序的數(shù)據(jù)文件以及求解逆序?qū)?shù)，最好、最壞、平均時間復(fù)雜度均為O(nlogn)，空間復(fù)雜度為O(n)；桶排序在數(shù)據(jù)分布均勻且分區(qū)粒度夠精細的情況下，其時間復(fù)雜度接近于O(n)，但空間復(fù)雜度將非常大。

 

一. 選擇排序

　　選擇排序(包括堆排序，Heapsort)是不穩(wěn)定，以一次索引交換代替三次值交換。選擇排序的交換操作介于 0 和 (n - 1） 次之間，比較操作為n (n - 1) / 2 次之間，賦值操作介于 0 和 3 (n - 1） 次之間。