復(fù)雜度以及穩(wěn)定性比較
| 排序算法 | 時(shí)間復(fù)雜度 | 穩(wěn)定排序 | 空間復(fù)雜度 |
|---|---|---|---|
| 冒泡排序 | O(n2) | 是 | O(1) |
| 插入排序 | O(n2) | 是 | O(1) |
| 希爾排序 | O(n3/2 | 否 | O(1) |
| 選擇排序 | O(n2) | 否 | O(1) |
| 快速排序 | O(nlog2(n) | 否 | O(1) |
| 歸并排序 | O(nlog2(n) | 是 | O(n) |
| 計(jì)數(shù)排序 | O(n+k)k為數(shù)據(jù)范圍 | 是 | O(n+k) |
| 桶排序 | O(n) | 是 | O(n) |
| 基數(shù)排序 | O(dn),d是維度 | 是 | O(n) |
數(shù)據(jù)集&運(yùn)行時(shí)間
以下數(shù)據(jù)集均包含10w個(gè)整數(shù)，根據(jù)數(shù)據(jù)特征分為: 完全相同椰拒、完全不同晶渠、完全隨機(jī)三類凰荚。各個(gè)算法的實(shí)現(xiàn)參考排序算法實(shí)現(xiàn).
完全相同
產(chǎn)生完全相同數(shù)據(jù)參考代碼如下:
func NewSameValue(number int) Value {
rand.Seed(1)
v := make(Value, number)
maxNumber := number
va := rand.Intn(maxNumber)
for i := 0; i < number; i++ {
v[i] = va
}
return v
}
運(yùn)行時(shí)間：
image.png
完全不同
參考代碼：
func NewDifferentValue(number int) Value {
rand.Seed(1)
tmp := make(Value, number)
for i := 0; i < number; i++ {
tmp[i] = i
}
va := make(Value, number)
for i := 0; i < number; i++ {
index := rand.Intn(number - i)
va[i] = tmp[index]
tmp[index] = tmp[len(tmp)-i-1]
}
return va
}
運(yùn)行時(shí)間
image.png
完全隨機(jī)
參考代碼：
func NewValue(number int) Value {
rand.Seed(1)
v := make(Value, number)
maxNumber := number
for i := 0; i < number; i++ {
v[i] = rand.Intn(maxNumber)
}
return v
}
運(yùn)行時(shí)間
image.png
