回顾一下计数排序
桶排序,是计数排序的升级版。解决了计数排序遗留的问题,当一组数据的最小值是100的时候,基数排序创建的空间是0-100-n个。浪费了0-100的位置,所以不能再使用0作为起点,但是总所周知程序的数组下标都是从〇开始的。所以我们需要解决的就是这个基数位置。
原理描述
如有数组 [98 80 94 95 85 94 85 84 98 96 95],按照计数排序的规则,我们需要创建的空间数组为0-98 [0,0,0,0,0,0,0,……0] ,但是由于数组中最小值为80,造成了空间的浪费。
对于这种情况,我们需要请出桶排序。我们以80为基数创建一个数组。

然后使用计数排序方法操作即可。
代码实现
Go
package main
import "fmt"
func main() {
//一个数组,其中有许多重复数据。
//numbers := []int{1, 3, 5, 0, 1, 2, 4, 4, 0, 3, 2, 5, 3}
//****为了体现效果,我们重新声明一个最小值为80的数组。****
numbers := []int{98, 80, 94, 95, 85, 94, 85, 84, 98, 96, 95}
fmt.Printf("排序前:%v\n", numbers)
//统计数组长度
length := len(numbers)
//找出最大值
maxNumber := numbers[0] //默认第一位最大
//****同时找到最小值****
minNumber := numbers[0] //默认第一位最小
//查找对比第二位及其以后的数字,找到最大。
for i := 1; i < length; i++ {
if maxNumber < numbers[i] {
maxNumber = numbers[i]
}
if minNumber > numbers[i] {
minNumber = numbers[i]
}
}
//用最大值减去最小值的差来创建数组。
counters := make([]int, (maxNumber-minNumber)+1) //由于数组的下标从0开始,所以创建数组为 0 - (n-1),创建0-n的数组,需要n+1
//开始计数
for i := 0; i < length; i++ {
//桶排序里边最重要的就是查找到数据的位置。
counters[numbers[i]-minNumber]++
}
exIndex := 0
fmt.Println("统计数据:")
//展开数组实现排序
for number, count := range counters {
fmt.Printf("统计到%d个:%d\n", count, number+minNumber) //显示统计到的数据
//展开数组实现排序
for i := 0; i < count; i++ {
numbers[exIndex] = number + minNumber
exIndex++
}
}
//fmt.Printf("统计数据:\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)
# 找出数据最大值
maxNum = numbers[0]
minNum = numbers[0]
for num in numbers:
if num > maxNum:
maxNum = num
if num < minNum:
minNum = num
# 声明统计数组
counters = [0] * (maxNum - minNum + 1)
# 开始计数
for num in numbers:
counters[num - minNum] += 1
# 统计完毕,展开数组
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)

网友评论