回顧一下計(jì)數(shù)排序
桶排序掺栅，是計(jì)數(shù)排序的升級(jí)版冗澈。解決了計(jì)數(shù)排序遺留的問題馏颂，當(dāng)一組數(shù)據(jù)的最小值是100的時(shí)候示血，基數(shù)排序創(chuàng)建的空間是0-100-n個(gè)。浪費(fèi)了0-100的位置救拉，所以不能再使用0作為起點(diǎn)难审，但是總所周知程序的數(shù)組下標(biāo)都是從〇開始的。所以我們需要解決的就是這個(gè)基數(shù)位置亿絮。
原理描述
如有數(shù)組 [98 80 94 95 85 94 85 84 98 96 95]告喊，按照計(jì)數(shù)排序的規(guī)則，我們需要?jiǎng)?chuàng)建的空間數(shù)組為0-98 [0,0,0,0,0,0,0,……0] 派昧，但是由于數(shù)組中最小值為80黔姜，造成了空間的浪費(fèi)。
對(duì)于這種情況蒂萎，我們需要請(qǐng)出桶排序秆吵。我們以80為基數(shù)創(chuàng)建一個(gè)數(shù)組。
image
然后使用計(jì)數(shù)排序方法操作即可五慈。
代碼實(shí)現(xiàn)
Go
package main
import "fmt"
func main() {
//一個(gè)數(shù)組纳寂，其中有許多重復(fù)數(shù)據(jù)。
//numbers := []int{1, 3, 5, 0, 1, 2, 4, 4, 0, 3, 2, 5, 3}
//****為了體現(xiàn)效果泻拦，我們重新聲明一個(gè)最小值為80的數(shù)組毙芜。****
numbers := []int{98, 80, 94, 95, 85, 94, 85, 84, 98, 96, 95}
fmt.Printf("排序前：%v\n", numbers)
//統(tǒng)計(jì)數(shù)組長(zhǎng)度
length := len(numbers)
//找出最大值
maxNumber := numbers[0] //默認(rèn)第一位最大
//****同時(shí)找到最小值****
minNumber := numbers[0] //默認(rèn)第一位最小
//查找對(duì)比第二位及其以后的數(shù)字，找到最大争拐。
for i := 1; i < length; i++ {
if maxNumber < numbers[i] {
maxNumber = numbers[i]
}
if minNumber > numbers[i] {
minNumber = numbers[i]
}
}
//用最大值減去最小值的差來創(chuàng)建數(shù)組腋粥。
counters := make([]int, (maxNumber-minNumber)+1) //由于數(shù)組的下標(biāo)從0開始，所以創(chuàng)建數(shù)組為 0 - （n-1）陆错，創(chuàng)建0-n的數(shù)組灯抛，需要n+1
//開始計(jì)數(shù)
for i := 0; i < length; i++ {
//桶排序里邊最重要的就是查找到數(shù)據(jù)的位置。
counters[numbers[i]-minNumber]++
}
exIndex := 0
fmt.Println("統(tǒng)計(jì)數(shù)據(jù)：")
//展開數(shù)組實(shí)現(xiàn)排序
for number, count := range counters {
fmt.Printf("統(tǒng)計(jì)到%d個(gè)：%d\n", count, number+minNumber) //顯示統(tǒng)計(jì)到的數(shù)據(jù)
//展開數(shù)組實(shí)現(xiàn)排序
for i := 0; i < count; i++ {
numbers[exIndex] = number + minNumber
exIndex++
}
}
//fmt.Printf("統(tǒng)計(jì)數(shù)據(jù):\n", counters)
fmt.Printf("排序后：%v\n", numbers)
}
Python
# -*- coding: UTF-8 -*-
numbers = [98, 80, 94, 95, 85, 94, 85, 84, 98, 96, 95]
print("排序前：", numbers)
# 找出數(shù)據(jù)最大值
maxNum = numbers[0]
minNum = numbers[0]
for num in numbers:
if num > maxNum:
maxNum = num
if num < minNum:
minNum = num
# 聲明統(tǒng)計(jì)數(shù)組
counters = [0] * (maxNum - minNum + 1)
# 開始計(jì)數(shù)
for num in numbers:
counters[num - minNum] += 1
# 統(tǒng)計(jì)完畢音瓷，展開數(shù)組
sortIndex = 0
for num in range(minNum, maxNum + 1):
while counters[num - minNum] > 0:
numbers[sortIndex] = num
sortIndex += 1
counters[num - minNum] -= 1
print("排序后：", numbers)
長(zhǎng)按二維碼關(guān)注我們
