# 算法:桶排序

作者: 小码侠 | 来源:发表于2018-10-31 22:33 被阅读3次

回顾一下计数排序

算法:计数排序

桶排序,是计数排序的升级版。解决了计数排序遗留的问题,当一组数据的最小值是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为基数创建一个数组。

image

然后使用计数排序方法操作即可。

代码实现

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)

长按二维码关注我们

相关文章

  • 线性排序

    桶排序、计数排序、基数排序 一、线性排序算法介绍 1.线性排序算法包括桶排序、计数排序、基数排序。2.线性排序算法...

  • 浅谈排序算法

    排序算法有很多种,今天先谈谈一些简单的排序算法。包括桶排序、冒泡排序和快速排序算法。后期总结各种排序算法。 桶排序...

  • 排序算法(十一)桶排序

    排序算法(十一)桶排序   桶排序(Bucket sort)是计数排序改进版,同样属于非比较排序,该算法的基本思想...

  • (转)排序算法

    排序算法点这里 数据结构与算法——计数排序、桶排序、基数排序

  • 排序算法三(桶,计数,基数)

    桶排序,计数排序,基数排序算法的时间复杂度都是线性的,所以把这类排序算法叫作线性排序。 桶排序 概念:将要排序的数...

  • 桶排序与哈希桶排序

    一.桶排序 算法原理 桶排序 (箱排序)的原理是将待排序序列分到有限数量的桶里面,然后对每个桶再分别排序(可以使用...

  • noip普及组3:排序算法

    排序算法 ①冒泡排序:O() ②插入排序:O() ③选择排序:O() ④桶排序 ⑤sort排序

  • 线性排序

    一、线性排序算法介绍 线性排序算法包括桶排序、计数排序、基数排序。 线性排序算法的时间复杂度为O(n)。 此3种排...

  • 桶排序、计数排序、基数排序

    一、线性排序算法介绍 线性排序算法包括桶排序、计数排序、基数排序。 线性排序算法的时间复杂度为O(n)。 此3种排...

  • 排序算法概述

    十大排序算法:冒泡排序,选择排序,插入排序,归并排序,堆排序,快速排序、希尔排序、计数排序,基数排序,桶排序 算法...

网友评论

本文标题:# 算法:桶排序

本文链接:https://www.haomeiwen.com/subject/uoiztqtx.html