一臀叙、桶排序
原理
桶排序（Bucket sort）或所謂的箱排序凯力，是一個(gè)排序算法猖辫，工作的原理是將數(shù)組分到有限數(shù)量的桶里切威。每個(gè)桶再個(gè)別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進(jìn)行排序），最后依次把各個(gè)桶中的記錄列出來記得到有序序列冕房。桶排序是鴿巢排序的一種歸納結(jié)果躏啰。當(dāng)要被排序的數(shù)組內(nèi)的數(shù)值是均勻分配的時(shí)候趁矾，桶排序使用線性時(shí)間（Θ(n)）耙册。但桶排序并不是比較排序，他不受到O(n log n)下限的影響毫捣。
基本思想
桶排序的思想近乎徹底的分治思想详拙。
桶排序假設(shè)待排序的一組數(shù)均勻獨(dú)立的分布在一個(gè)范圍中，并將這一范圍劃分成幾個(gè)子范圍（桶）蔓同。
然后基于某種映射函數(shù)f 饶辙，將待排序列的關(guān)鍵字 k 映射到第i個(gè)桶中 (即桶數(shù)組B 的下標(biāo)i) ，那么該關(guān)鍵字k 就作為 B[i]中的元素 (每個(gè)桶B[i]都是一組大小為N/M 的序列 )斑粱。
接著將各個(gè)桶中的數(shù)據(jù)有序的合并起來 : 對(duì)每個(gè)桶B[i] 中的所有元素進(jìn)行比較排序 (可以使用快排)弃揽。然后依次枚舉輸出 B[0]….B[M] 中的全部?jī)?nèi)容即是一個(gè)有序序列。
補(bǔ)充： 映射函數(shù)一般是 f = array[i] / k; k^2 = n; n是所有元素個(gè)數(shù)
為了使桶排序更加高效，我們需要做到這兩點(diǎn)：
- 在額外空間充足的情況下矿微，盡量增大桶的數(shù)量
- 使用的映射函數(shù)能夠?qū)⑤斎氲?N 個(gè)數(shù)據(jù)均勻的分配到 K 個(gè)桶中
同時(shí)痕慢，對(duì)于桶中元素的排序，選擇何種比較排序算法對(duì)于性能的影響至關(guān)重要涌矢。
實(shí)現(xiàn)邏輯
- 設(shè)置一個(gè)定量的數(shù)組當(dāng)作空桶子掖举。
- 尋訪序列，并且把項(xiàng)目一個(gè)一個(gè)放到對(duì)應(yīng)的桶子去娜庇。
- 對(duì)每個(gè)不是空的桶子進(jìn)行排序塔次。
- 從不是空的桶子里把項(xiàng)目再放回原來的序列中。
動(dòng)畫演示過程
Go語言描述
桶排序：通過開辟另外空間并分配+收集的排序方法
- 平均時(shí)間復(fù)雜度：O(n*k)
- 最壞時(shí)間復(fù)雜度：O(n2)
- 最好時(shí)間復(fù)雜度：O(n)
- 空間復(fù)雜度：O(n*k)
- 穩(wěn)定性：穩(wěn)定
func BucketSort(list []int, size int) {
min := list[0]
max := list[0]
for i := 0; i < len(list); i++ {
if min > list[i] {
min = list[i]
}
if max < list[i] {
max = list[i]
}
}
// 桶切片初始化
count := make([][]int, (max-min)/size+1)
// 數(shù)據(jù)入桶
for i := 0; i < len(list); i++ {
count[(list[i]-min)/size] = append(count[(list[i]-min)/size], list[i])
}
key := 0
// 對(duì)每個(gè)桶進(jìn)行排序
for _, bucket := range count {
if len(bucket) <= 0 {
continue
}
// 插入排序
InsertionSort(bucket)
for _, value := range bucket {
list[key] = value
key = key + 1
}
}
return
}
二名秀、計(jì)數(shù)排序
計(jì)數(shù)排序不是比較數(shù)值排序励负，是記錄數(shù)據(jù)出現(xiàn)次數(shù)的一種排序算法。它的原理有點(diǎn)類似桶排序算法匕得，可以看似特殊的桶排序算法熄守。
原理
算法解析：
- 找出待排數(shù)組中最大值；
- 額外一個(gè)數(shù)組記錄待排數(shù)組值出現(xiàn)的次數(shù)耗跛；
- 循環(huán)打印存儲(chǔ)數(shù)值次數(shù)的數(shù)組下標(biāo)值裕照；
動(dòng)畫演示過程
Go語言描述
- 計(jì)數(shù)排序 counting sort
- 平均時(shí)間復(fù)雜度：O(n*k)
- 最壞時(shí)間復(fù)雜度：O(n2)
- 最好時(shí)間復(fù)雜度：O(n)
- 空間復(fù)雜度：O(n*k)
- 穩(wěn)定性：穩(wěn)定
package sort
func CountingSort(list []int) {
// 初始化一個(gè)最大值，默認(rèn)第一元素
max := list[0]
l := len(list)
// 先找出最大值
for i := 1; i < l; i++ {
if max < list[i] {
max = list[i]
}
}
// 記錄該值的出現(xiàn)次數(shù)
arr := make([]int, max+1)
for j := 0; j < l; j++ {
arr[list[j]]++
}
// fmt.Println("arr:",arr)
pos := 0
for index, v := range arr {
for x := 0; x < v; x++ {
list[pos] = index
pos++
}
}
}
由于計(jì)數(shù)排序依賴于額外數(shù)組保存整數(shù)元素出現(xiàn)的次數(shù)调塌，需要開辟額外空間存儲(chǔ)損耗較大(典型的空間換時(shí)間)晋南，不適合太過大量和離散的值，只適合小而緊湊的序列值的排序羔砾。
