Java桶排序之基数排序详解

Java桶排序之基数排序详解

基本概念

基数排序(Radix Sort),又称桶排法(Bucket Sort),是一种非比较型整数排序算法。其思想是将一个数字序列拆分成多个数字进行比较排序,从个位开始,逐层进行排序,直到最高位排序完成。

实现步骤

  1. 初始化10个桶,代表数字0到9;
  2. 按照从低位到高位的顺序进行排序,首先比较个位,然后比较十位,以此类推,直到最高位;
  3. 把每次排序后得到的结果依次放回原序列中,重复第2步排序,直至最高位排序完成。

代码实现

以下为Java代码实现:

import java.util.Arrays;

public class RadixSort {
  public static void radixSort(int[] arr) {
    if (arr == null || arr.length < 2) {
      return;
    }
    int exp = 1;
    int max = getMax(arr);
    int[] temp = new int[arr.length];
    while (max / exp > 0) {
      int[] bucket = new int[10];
      for (int i = 0; i < arr.length; i++) {
        bucket[(arr[i] / exp) % 10]++;
      }
      for (int i = 1; i < bucket.length; i++) {
        bucket[i] += bucket[i - 1];
      }
      for (int i = arr.length - 1; i >= 0; i--) {
        temp[bucket[(arr[i] / exp) % 10] - 1] = arr[i];
        bucket[(arr[i] / exp) % 10]--;
      }
      System.arraycopy(temp, 0, arr, 0, arr.length);
      exp *= 10;
    }
  }

  public static int getMax(int[] arr) {
    int max = arr[0];
    for (int i = 1; i < arr.length; i++) {
      max = Math.max(max, arr[i]);
    }
    return max;
  }

  public static void main(String[] args) {
    int[] arr = { 170, 45, 75, 90, 802, 24, 2, 66 };
    System.out.println("排序前:" + Arrays.toString(arr));
    radixSort(arr);
    System.out.println("排序后:" + Arrays.toString(arr));
  }
}

示例解析

假设有以下数组:

{25, 34, 12, 10, 23, 45, 56, 74}

首先比较个位数,这个数组中个位数分别是:

{5, 4, 2, 0, 3, 5, 6, 4}

按照个位数依次分配到桶里面,桶的数量 = 0 ~ 9,将桶中元素复写到原数组中,原数组变成:

{10, 12, 23, 34, 25, 45, 56, 74}

接下来比较十位数,这个数组中十位数分别是:

{2, 3, 1, 0, 2, 4, 5, 7}

重复上述操作,依次分配到桶中,将桶中元素复写到原数组中,原数组变成:

{10, 12, 23, 25, 34, 45, 56, 74}

最后按照百位数比较排序,由于没有百位数,所以排序已完成,最终得到排序后的数组:

{10, 12, 23, 25, 34, 45, 56, 74}

总结

基数排序是一种非常高效的排序算法,它的时间复杂度为O(kn),其中k为数字的最高位数,n为数字个数,相较于快速排序的平均时间复杂度O(nlogn)更具优势。

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:Java桶排序之基数排序详解 - Python技术站

(0)
上一篇 2023年5月19日
下一篇 2023年5月19日

相关文章

  • java实现对map的字典序排序操作示例

    下面是Java实现对Map的字典序排序操作的完整攻略: 1. 根据键(Key)排序 1.1 实现方式一 Map<String, String> map = new HashMap<>(); map.put("b", "2"); map.put("c", "3&quo…

    算法与数据结构 2023年5月19日
    00
  • Python 数据结构之十大经典排序算法一文通关

    Python 数据结构之十大经典排序算法一文通关 一、前置知识 在学习本文之前,需要具备以下基础知识: Python 基础语法 算法与数据结构基础 二、十大经典排序算法 冒泡排序 选择排序 插入排序 希尔排序 归并排序 快速排序 堆排序 计数排序 桶排序 基数排序 本文将一一讲解这十种排序算法。 三、冒泡排序 冒泡排序是一种简单的排序算法,它重复地遍历过要排…

    算法与数据结构 2023年5月19日
    00
  • 华为笔试算法题汇总

    下面是“华为笔试算法题汇总”的完整攻略: 一、题目来源 本篇攻略总结了华为笔试中常见的算法题目,这些题目可以在华为科技招聘官网上的笔试环节中出现。 二、题目类型 华为笔试中常见的算法题目主要包括: 字符串操作:如字符串反转、字符串查找等; 数组排序:如快排、归并排序等; 链表操作:如链表反转、链表合并等; 动态规划问题:如背包问题、最长公共子序列等; 图论问…

    算法与数据结构 2023年5月19日
    00
  • c语言5个常用的排序算法实例代码

    C语言5个常用的排序算法实例代码 本文旨在讲解C语言中常用的5种排序算法,包括冒泡排序、选择排序、插入排序、快速排序和归并排序。以下将逐一介绍它们的实现过程,并提供示例代码。 冒泡排序(Bubble Sort) 算法思想:冒泡排序是一种简单的排序算法,它会首先比较相邻的元素,如果它们的顺序不正确,就交换它们的位置。这样一遍比较下来,最后一个元素就已经是最大的…

    算法与数据结构 2023年5月19日
    00
  • 希尔排序算法的C语言实现示例

    下面是“希尔排序算法的C语言实现示例”完整攻略。 希尔排序算法简介 希尔排序是通过将整个待排序数组分割成多个子序列,对每个子序列进行插入排序,然后逐步减少子序列长度,最终使整个序列有序的一种算法。 希尔排序算法的流程 按照一定的间隔将待排序数组分成若干个子序列; 对每个子序列进行插入排序,使其中的元素可以快速有序; 缩小排序间隔,重复执行步骤1和2; 直至排…

    算法与数据结构 2023年5月19日
    00
  • JavaScript插入排序算法原理与实现方法示例

    JavaScript插入排序算法原理与实现方法示例 算法原理 插入排序是一种简单直观的排序算法,其基本原理是将一个待排序的数组依次插入一个有序的数组中,使得最终生成的有序数组是全局有序的。每次将一个待排序的元素插入到有序数组中时,我们从有序数组的末尾开始比较,如果待排序的元素比当前比较的元素小,则交换位置,继续比较,否则插入到当前位置。 实现方法 下面是Ja…

    算法与数据结构 2023年5月19日
    00
  • JS常见面试试题总结【去重、遍历、闭包、继承等】

    来讲解一下“JS常见面试试题总结【去重、遍历、闭包、继承等】”的完整攻略。 一、去重 JS中去重的方法有很多种,我这里介绍两种比较常见的方法。 1.1 利用Set去重 let arr = [1, 2, 3, 1, 2, 3]; let unique = […new Set(arr)]; console.log(unique); // [1, 2, 3] …

    算法与数据结构 2023年5月19日
    00
  • Flutter Dart快速排序算法示例详解

    Flutter Dart快速排序算法示例详解 介绍 快速排序是一种排序算法,其基本思想是选择一个基准元素,将数组分成两个子数组,其中一个子数组的元素都比基准元素小,另一个子数组的元素都比基准元素大。然后递归地对两个子数组进行快速排序。 实现步骤 选择一个基准元素,并将其从数组中移除。 遍历数组,将小于基准元素的元素放入一个新的左侧数组中,大于基准元素的元素放…

    算法与数据结构 2023年5月19日
    00
合作推广
合作推广
分享本页
返回顶部