Java玩转《啊哈算法》排序之桶排序

这篇具有很好参考价值的文章主要介绍了Java玩转《啊哈算法》排序之桶排序。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

过去心不可得,现在心不可得,未来心不可得

楔子

大家好!本人最近看了下《啊哈算法》,写的确实不错,生动形象又有趣(我没收钱,确实如此 )。

但对我来说,稍显遗憾的是,书籍代码是c语言,而不是本人常用的Java。

那就弥补遗憾,说干就干,把这本书的示例语言用java给翻译一遍!!!

于是就有了本篇博客,当然这只是第一篇,主要是讲解桶排序。
Java玩转《啊哈算法》排序之桶排序,算法,java,算法,开发语言,排序算法

没有买纸质书的童鞋也甭担心,电子版的下载链接已经放到下方了,自己下载去吧!!!

链接:https://pan.baidu.com/s/1imxiElcCorw2F-HJEnB-PA?pwd=jmgs
提取码:jmgs

不过还是建议有条件的同学可以买下纸质书,尊重一下作者的劳动成果。

代码地址

本文代码已开源:

git clone https://gitee.com/guqueyue/my-blog-demo.git

请切换到gitee分支,

然后查看aHaAlgorithm模块下的src/main/java/com/guqueyue/aHaAlgorithm/chapter_1_Sort即可!

桶排序

算法学习千千万,排序是块敲门砖!!!

国内算法学习似乎有个不成文的规定,想学算法,先学排序。而桶排序可以说是排序算法中最简单的算法了。

Java玩转《啊哈算法》排序之桶排序,算法,java,算法,开发语言,排序算法

桶排序的核心原理非常简单:

遍历需要排序的元素集合,用一个数组表示。数组的一个个连续的空间作为一个个桶,索引为元素,而索引对应的值为元素个数。

相当于把元素放到对应的一个一个桶里面,所以叫桶排序。
Java玩转《啊哈算法》排序之桶排序,算法,java,算法,开发语言,排序算法

而因为数组的索引是连续的,所以遍历数组索引就能得到一个升序的元素集合。如果索引对应的值为0,说明该元素不存在。

代码

核心部分

	/**
     * @Description 桶排序
     * @Param [scoreArr]
     * @return int[]
     **/
    private static int[] bucketSort(int[] scoreArr) {

        // 11为数据范围的大小
        int[] bucket = new int[11];
        // 用于返回排序后的数组
        int[] result = new int[scoreArr.length];

        // 入桶,计数
        for (int num : scoreArr) {
            bucket[num]++;
        }

        // 根据桶的索引以及计数的次数,生成排序后的数组 - 如果需要降序,倒序遍历数组即可
        int k = 0;
        for (int i = 0; i < bucket.length; i++) { // 遍历每个桶
            for (int j = 0; j < bucket[i]; j++) { // 遍历桶里面的元素
                result[k++] = i;
            }
        }

        return result;
    }

优缺点

通过上文的讲解以及核心代码,我们不难得出桶排序具有以下的优缺点:

  • 优点:
    1. 简单
    2. 速度快。时间复杂度为:O(m+n), 其中m为排序数组的长度,n为桶的长度。
  • 缺点:
    1. 占用空间。空间复杂度为O(m+n),因为桶的长度取决于元素取值范围,元素取值范围越大,越占用空间。
    2. 有使用局限,只能对整数进行排序。若元素中存在小数无法使用桶排序,因为数组的索引不能为小数。

完整代码

package com.guqueyue.aHaAlgorithm.chapter_1_Sort;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @Author: guqueyue
 * @Description: 桶排序
 * @Date: 2024/1/8
 **/
public class BucketSort {

    public static void main(String[] args) {

        // 获取分数数组
        int[] scoreArr = getScoreArr();
        System.out.println("输入的数组为: " + Arrays.toString(scoreArr));

        // 桶排序
        int[] result = bucketSort(scoreArr);
        System.out.println("排序后:" + Arrays.toString(result));
    }

    /**
     * @Description 桶排序
     * @Param [scoreArr]
     * @return int[]
     **/
    private static int[] bucketSort(int[] scoreArr) {

        // 11为数据范围的大小
        int[] bucket = new int[11];
        // 用于返回排序后的数组
        int[] result = new int[scoreArr.length];

        // 入桶,计数
        for (int num : scoreArr) {
            bucket[num]++;
        }

        // 根据桶的索引以及计数的次数,生成排序后的数组 - 如果需要降序,倒序遍历数组即可
        int k = 0;
        for (int i = 0; i < bucket.length; i++) { // 遍历每个桶
            for (int j = 0; j < bucket[i]; j++) { // 遍历桶里面的元素
                result[k++] = i;
            }
        }

        return result;
    }

    /**
     * @Description 获取分数数组
     * @Param []
     * @return int[]
     **/
    private static int[] getScoreArr() {
        Scanner scanner = new Scanner(System.in);

        System.out.print("请输入数组长度:");
        int n = scanner.nextInt();

        int[] scoreArr = new int[n];
        for (int i = 0; i < n; i++) {
            System.out.printf("请输入第%d个数(范围:0-10),然后按回车: ", i+1);
            scoreArr[i] = scanner.nextInt();
        }

        return scoreArr;
    }
}

演示

运行代码,控制台输入可得:
Java玩转《啊哈算法》排序之桶排序,算法,java,算法,开发语言,排序算法

升级版

正如作者所说,上文演示的只是一个简易版的桶排序算法。

那如果需要输入多个学生的姓名和分数,再根据学生的分数排名由高到低输出学生的姓名,这样要怎么做呢?

作者这里并没有给出答案,我们来扩展一下,首先创建一个学生类:

package com.guqueyue.aHaAlgorithm.entity;

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;

/**
 * @Author: guqueyue
 * @Description: 学生类
 * @Date: 2024/1/9
 **/
//lombok插件的注解
@Data // 若未使用lombok插件,请自行生成getter、setter以及toString方法
@NoArgsConstructor // 若未使用lombok插件,请自行生成无参构造方法
@AllArgsConstructor // 若未使用lombok插件,请自行生成有参构造方法
public class Student {

    private String name; // 姓名
    private Integer score; // 分数
}

核心代码

同理,我们使用桶排序,得到一个通过分数降序排序的学生数组:

	/**
     * @Description 桶排序 - 通过分数排序学生数组
     * @Param [scoreArr]
     * @return com.guqueyue.aHaAlgorithm.entity.Student[]
     **/
    private static Student[] bucketSort(Student[] scoreArr) {

        Student[] result = new Student[scoreArr.length];
        // 桶排序,将分数入桶
        int[] bucket = new int[101];
        for (Student student : scoreArr) {
            bucket[student.getScore()]++;
        }

        int k = 0;
        for (int i = 100; i >= 0; i--) { // 倒序遍历桶
            if (bucket[i] > 0) {
                for (Student student : scoreArr) { // 遍历学生数组,将符合当前桶的分数的学生放入数组
                    if (student.getScore() == i) {
                        result[k++] = student;
                    }
                }
            }
        }

        return result;
    }

完整代码

package com.guqueyue.aHaAlgorithm.chapter_1_Sort;

import com.guqueyue.aHaAlgorithm.entity.Student;

import java.util.*;

/**
 * @Author: guqueyue
 * @Description: 桶排序 - 通过分数排序学生数组
 * @Date: 2024/1/9
 **/
public class BucketSort2 {
    public static void main(String[] args) {

        Student[] scoreArr = getStudentArr(); // 获取学生数组
        System.out.println("输入的数组为:" + Arrays.toString(scoreArr));

        Student[] result = bucketSort(scoreArr);
        System.out.println("排序后的数组为: " + Arrays.toString(result));

        System.out.print("学生排名为: ");
        for (Student student : result) {
            System.out.print(student.getName() + " ");
        }
        System.out.println();
    }

    /**
     * @Description 桶排序 - 通过分数排序学生数组
     * @Param [scoreArr]
     * @return com.guqueyue.aHaAlgorithm.entity.Student[]
     **/
    private static Student[] bucketSort(Student[] scoreArr) {

        Student[] result = new Student[scoreArr.length];
        // 桶排序,将分数入桶
        int[] bucket = new int[101];
        for (Student student : scoreArr) {
            bucket[student.getScore()]++;
        }

        int k = 0;
        for (int i = 100; i >= 0; i--) { // 倒序遍历桶
            if (bucket[i] > 0) {
                for (Student student : scoreArr) { // 遍历学生数组,将符合当前桶的分数的学生放入数组
                    if (student.getScore() == i) {
                        result[k++] = student;
                    }
                }
            }
        }

        return result;
    }

    /**
     * @Description 桶排序优化版 - 通过分数排序学生数组
     * @Param [scoreArr]
     * @return com.guqueyue.aHaAlgorithm.entity.Student[]
     **/
    private static Student[] bucketSort2(Student[] scoreArr) {

        // 1.构建 分数 -> 人名集合 映射集
        Map<Integer, List<Student>> dict = new HashMap<>();
        for (Student student : scoreArr) {

            Integer score = student.getScore();
            List<Student> studentList = new ArrayList<>();
            if (dict.containsKey(score)) {
                studentList = dict.get(score);
            }

            studentList.add(student);
            dict.put(score, studentList);
        }

        Student[] result = new Student[scoreArr.length];
        // 桶排序
        int[] bucket = new int[101];
        for (Student student : scoreArr) {
            bucket[student.getScore()]++;
        }

        int k = 0;
        for (int i = 100; i >= 0; i--) {
            if (bucket[i] > 0) { // 如果有
                List<Student> students = dict.get(i);
                if (students != null && students.size() > 0) {
                    for (Student student : students) {
                        result[k++] = student;
                    }
                }
            }
        }

        return result;
    }

    /**
     * @Description 获取学生数组
     * @Param []
     * @return com.guqueyue.aHaAlgorithm.entity.Student[]
     **/
    private static Student[] getStudentArr() {
        Scanner scanner = new Scanner(System.in);

        System.out.print("请输入学生数量:");
        int n = scanner.nextInt();
        Student[] students = new Student[n];

        for (int i = 0; i < n; i++) {
            Student student = new Student();

            System.out.printf("请输入第%d个学生的姓名:", i+1);
            student.setName(scanner.next());
            System.out.printf("请输入第%d个学生的分数(0-100):", i+1);
            student.setScore(scanner.nextInt());

            students[i] = student;
        }

        return students;
    }
}

演示

运行代码,控制台输入,可得:
Java玩转《啊哈算法》排序之桶排序,算法,java,算法,开发语言,排序算法

课后习题

发一道力扣的题目链接当课后习题吧,终于有一种老师给学生布置作业的感觉了:

912. 排序数组

Java玩转《啊哈算法》排序之桶排序,算法,java,算法,开发语言,排序算法

如果理解了桶排序的含义的话,这题应该是很简单的。

唯一的难点在于,元素的取值范围是负数的话,该如何用数组的索引表示呢?

但我相信难不倒你们 (^_−)☆

我们下期博客再见!文章来源地址https://www.toymoban.com/news/detail-823862.html

到了这里,关于Java玩转《啊哈算法》排序之桶排序的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【经典题】跟着凡人玩转C语言之快速排序算法

     💘作者:你我皆为凡人  💘博客主页:你我皆为凡人的博客  💘名言警句:时间不会为任何人停留,而事物与人,无时不刻也在变化着。每一个人,也都在不停向前!  💘觉得博主文章写的不错的话,希望大家三连(✌关注,✌点赞,✌评论),多多支持一下!!  💘其他作

    2023年04月11日
    浏览(38)
  • 玩转快速排序(C语言版)

    W...Y的主页 😊 代码仓库分享  💕 🍔前言: 本篇文章,我们来讲解一下神秘的快速排序。对于快速排序我相信大家都已经有所耳闻,但是快速排序是有很多的版本的。我们这次的目的就是快排的所有内容搞懂,废话不多说,让我们开始今天的内容。 🍟目录 快排的介绍

    2024年02月08日
    浏览(47)
  • 十大排序算法及Java中的排序算法

    常见的排序算法有十种,可以分为以下两大类: 非线性时间比较类排序 :通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(n log n),因此称为非线性时间比较类排序 线性时间非比较类排序 :不通过比较来决定元素间的相对次序,它可以突破基于比较排序的时

    2024年02月08日
    浏览(46)
  • 【Java】使用 Java 语言实现一个冒泡排序

    大家好,我是全栈小5,欢迎阅读小5的系列文章。 这是《Java》系列文章,每篇文章将以博主理解的角度展开讲解, 特别是针对知识点的概念进行叙说,大部分文章将会对这些概念进行实际例子验证,以此达到加深对知识点的理解和掌握。 温馨提示:博主能力有限,理解水平

    2024年03月22日
    浏览(42)
  • JAVA算法(二)排序算法

    定义:相邻的数据两两比较,小的 放前面,大的放后面 过程: 相邻的元素两两比较,小的放左边,大的放右边。 第一轮比较完毕之后,最大值就已经确定,第二轮可以少循环一次,后面以此类推。 如果数组中有n个数据,总共我们只要执行n-1轮的代码就可以。 定义: 从0索

    2024年02月05日
    浏览(38)
  • 排序之玩转qsort函数——【C语言】

    说起排序,我们会想起许多算法,在之前的博客中我也写到过,比如:冒泡排序法、快速排序法、选择排序法等等。其实在C语言中一直有一个可以将数组中的内容进行排序的函数且功能完善内容齐全的库函数——qsort函数。今天就让我们来探索一下吧! 目录 回调函数 初始

    2024年02月13日
    浏览(47)
  • Java 与排序算法(1):冒泡排序

    冒泡排序(Bubble Sort)是一种简单的排序算法,它的基本思想是通过不断交换相邻两个元素的位置,使得较大的元素逐渐往后移动,直到最后一个元素为止。冒泡排序的时间复杂度为 O ( n 2 ) O(n^2) O ( n 2 ) ,空间复杂度为 O ( 1 ) O(1) O ( 1 ) ,是一种稳定的排序算法。 其实现过程

    2024年02月11日
    浏览(44)
  • 【Java面试题】Java基础——排序算法

    冒泡排序★★★ 冒泡排序(Bubble Sort)也是一种简单直观的排序算法。 它重复的遍历过要排序的数列, 一次比较相邻的两个元素,如果他们的顺序错误就把他们交换过来 。 这个算法的名字由来是因为越大的元素会经由交换慢慢\\\"浮\\\"到最后面。 当然,大家可以按照从大到小的

    2024年02月12日
    浏览(34)
  • 桶排序(Java语言)

     视频讲解地址:【手把手带你写十大排序】8.桶排序(Java语言)_哔哩哔哩_bilibili 代码:

    2024年01月17日
    浏览(88)
  • Java 语言实现冒泡排序

    冒泡排序是一种简单直观的排序算法,它重复地比较相邻的两个元素,如果顺序错误就交换它们,直到没有需要交换的元素为止。冒泡排序的思路是通过每一轮的比较将最大(或最小)的元素逐渐“冒泡”到数组的最后,并将其固定在正确的位置上。 Java作为一种高级语言,

    2024年02月10日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包