楔子
大家好!本人最近看了下《啊哈算法》,写的确实不错,生动形象又有趣(我没收钱,确实如此 )。
但对我来说,稍显遗憾的是,书籍代码是c语言,而不是本人常用的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
即可!
桶排序
算法学习千千万,排序是块敲门砖!!!
国内算法学习似乎有个不成文的规定,想学算法,先学排序。而桶排序可以说是排序算法中最简单的算法了。
桶排序的核心原理非常简单:
遍历需要排序的元素集合,用一个数组表示。数组的一个个连续的空间作为一个个桶,索引为元素,而索引对应的值为元素个数。
相当于把元素放到对应的一个一个桶里面,所以叫桶排序。
而因为数组的索引是连续的,所以遍历数组索引就能得到一个升序的元素集合。如果索引对应的值为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;
}
优缺点
通过上文的讲解以及核心代码,我们不难得出桶排序具有以下的优缺点:
- 优点:
- 简单。
- 速度快。时间复杂度为:O(m+n), 其中m为排序数组的长度,n为桶的长度。
- 缺点:
- 占用空间。空间复杂度为O(m+n),因为桶的长度取决于元素取值范围,元素取值范围越大,越占用空间。
- 有使用局限,只能对整数进行排序。若元素中存在小数无法使用桶排序,因为数组的索引不能为小数。
完整代码
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;
}
}
演示
运行代码,控制台输入可得:
升级版
正如作者所说,上文演示的只是一个简易版的桶排序算法。
那如果需要输入多个学生的姓名和分数,再根据学生的分数排名由高到低输出学生的姓名,这样要怎么做呢?
作者这里并没有给出答案,我们来扩展一下,首先创建一个学生类:
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;
}
}
演示
运行代码,控制台输入,可得:
课后习题
发一道力扣的题目链接当课后习题吧,终于有一种老师给学生布置作业的感觉了:
912. 排序数组
如果理解了桶排序的含义的话,这题应该是很简单的。
唯一的难点在于,元素的取值范围是负数的话,该如何用数组的索引表示呢?
但我相信难不倒你们 (^_−)☆文章来源:https://www.toymoban.com/news/detail-823862.html
我们下期博客再见!文章来源地址https://www.toymoban.com/news/detail-823862.html
到了这里,关于Java玩转《啊哈算法》排序之桶排序的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!