排序法

平均時(shí)間

最差情形

穩(wěn)定度

空間復(fù)雜度

備注

冒泡 

 O(n2)

  O(n2)

  穩(wěn)定

 O(1)

n小時(shí)較好

交換               

 O(n2) 

 O(n2) 

不穩(wěn)定

O(1)

n小時(shí)較好

選擇

O(n2)

O(n2)

不穩(wěn)定

O(1)

n小時(shí)較好

插入

O(n2)

O(n2)

穩(wěn)定

O(1)

大部分已排序時(shí)較好

基數(shù)

O(nlogRB)

O(nlogRB)

穩(wěn)定

O(n)

B是真數(shù)(0-9)， R是基數(shù)(個(gè)十百)

Shell

O(nlogn)

O(ns) 1<s<2

不穩(wěn)定

O(1)

s是所選分組

快速

O(nlogn)

O(n2)

不穩(wěn)定

O(nlogn)

n大時(shí)較好

歸并

O(nlogn)

O(nlogn)

穩(wěn)定

O(1)

n大時(shí)較好

堆

O(nlogn)

O(nlogn)

不穩(wěn)定

O(1)

n大時(shí)較好