计数排序

计数排序，针对数据重复度比较高的数组。将数据转化为数组下标存储在新的统计数组中，然后依次遍历原数组，统计元素出现次数。最后再展开统计数组，实现排序。计数排序要求原数据必须是有确定范围的整数。

动画演示

countingSort.gif

代码实现

Go

package main

import "fmt"

func main() {
    //一个数组，其中有许多重复数据。
    numbers := []int{1, 3, 5, 0, 1, 2, 4, 4, 0, 3, 2, 5, 3}

    fmt.Printf("排序前：%v\n", numbers)
    //统计数组长度
    length := len(numbers)

    //找出最大值
    maxNumber := numbers[0] //默认第一位最大
    //查找对比第二位及其以后的数字，找到最大。
    for i := 1; i < length; i++ {
        if maxNumber < numbers[i] {
            maxNumber = numbers[i]
        }
    }

    //用最大值创建一个数组
    counters := make([]int, maxNumber+1) //由于数组的下标从0开始，所以创建数组为 0 - （n-1），创建0-n的数组，需要n+1

    //开始计数
    for i := 0; i < length; i++ {
        counters[numbers[i]]++
    }

    exIndex := 0

    fmt.Println("统计数据：")
    //展开数组实现排序
    for number, count := range counters {
        fmt.Printf("统计到%d个：%d\n", count, number) //显示统计到的数据

        //展开数组实现排序
        for i := 0; i < count; i++ {
            numbers[exIndex] = number
            exIndex++
        }
    }
    //fmt.Printf("统计数据:\n", counters)
    fmt.Printf("排序后：%v\n", numbers)
}

Python

# -*- coding: UTF-8 -*-

numbers = [1, 3, 5, 0, 1, 2, 4, 4, 0, 3, 2, 5, 3]

print("排序前：", numbers)

# 找出数据最大值
maxNum = numbers[0]
for num in numbers:
    if num > maxNum:
        maxNum = num

# 声明统计数组
counters = [0] * (maxNum + 1)

# 开始计数
for num in numbers:
    counters[num] += 1

# 统计完毕，展开数组
sortIndex = 0
for num in range(maxNum + 1):
    while counters[num] > 0:
        numbers[sortIndex] = num
        sortIndex += 1
        counters[num] -= 1

print("排序后：", numbers)

疑问？

如果数组的最小元素是100乃至更大的数怎么办？

长按二维码关注我们