基于比較排序算法時(shí)間下限為O(nlogn)，計(jì)數(shù)排序時(shí)間復(fù)雜度O(n)。
在待排序列基本有序的情況下，直接插入排序是最佳排序算法；快速排序的效率一般情況下都比較高，但在待排序列基本有序的情況下，時(shí)間復(fù)雜度接近 O(n2)；歸并排序效率僅次于快速排序，是穩(wěn)定排序，經(jīng)常用于多個(gè)有序的數(shù)據(jù)文件歸并成一個(gè)有序的數(shù)據(jù)文件以及求解逆序?qū)?shù)，最好、最壞、平均時(shí)間復(fù)雜度均為O(nlogn)，空間復(fù)雜度為O(n)；桶排序在數(shù)據(jù)分布均勻且分區(qū)粒度夠精細(xì)的情況下，其時(shí)間復(fù)雜度接近于O(n)，但空間復(fù)雜度將非常大。
一. 選擇排序
選擇排序(包括堆排序，Heapsort)是不穩(wěn)定，以一次索引交換代替三次值交換。選擇排序的交換操作介于 0 和 (n - 1） 次之間，比較操作為n (n - 1) / 2 次之間，賦值操作介于 0 和 3 (n - 1） 次之間。
算法描述：每一次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€(gè)元素位置，然后與無序區(qū)的首元素進(jìn)行交換，直到全部待排序的數(shù)據(jù)元素排完。比如[31,5,8,1,9,2,4,26,7]這個(gè)數(shù)組包含9個(gè)元素，在第一輪排序中需要8次比較才能找到最小值1；但是在8次比較中都只記錄較小值的索引，而不必做3次值交換，值交換是在上述步驟完成之后才發(fā)生的，且僅一次
