【唐叔学算法】第21天:超越比较-计数排序、桶排序与基数排序的Java实践及性能剖析

server/2024/12/26 11:14:50/

非比较排序:计数排序、桶排序与基数排序的深度解析与Java实现

引言

当我们谈论排序算法时,大多数人的第一反应可能是基于元素比较的排序方法,如快速排序或归并排序。然而,存在一类特殊的排序算法——非比较排序,它们不依赖于元素之间的直接比较来决定顺序,而是利用数据本身的特性进行排序。这类算法在特定场景下具有显著的优势,可以提供比 O(n log n) 更好的时间复杂度,尤其是在处理整数或有限范围的数据时。本文将深入探讨三种典型的非比较排序算法计数排序桶排序基数排序,分析它们的原理、实现细节、时间复杂度和空间复杂度,并通过Java代码进行具体实现。

计数排序:基于计数的线性排序算法

算法原理

计数排序(Counting Sort)是一种线性时间复杂度的排序算法,适用于待排序元素的范围已知且较小的场景。其核心思想是通过统计每个元素出现的次数,然后根据统计结果将元素直接放置到正确的位置。

算法步骤

  1. 找出待排序序列中的最大值和最小值。
  2. 创建一个计数数组,长度为最大值与最小值之差加1,用于统计每个元素出现的次数。
  3. 遍历待排序序列,填充计数数组。
  4. 根据计数数组,将元素按顺序放回原序列。

时间复杂度与空间复杂度

  • 时间复杂度:O(n + k),其中n是序列的长度,k是元素的范围(最大值与最小值之差)。
  • 空间复杂度:O(k),需要额外的计数数组来存储统计结果。

Java实现

public class CountingSort {public static void countingSort(int[] arr) {if (arr == null || arr.length == 0) {return;}// 找出最大值和最小值int max = arr[0], min = arr[0];for (int num : arr) {if (num > max) max = num;if (num < min) min = num;}// 创建计数数组int[] count = new int[max - min + 1];// 统计每个元素出现的次数for (int num : arr) {count[num - min]++;}// 根据计数数组重构排序后的数组int index = 0;for (int i = 0; i < count.length; i++) {while (count[i] > 0) {arr[index++] = i + min;count[i]--;}}}public static void main(String[] args) {int[] arr = {4, 2, 2, 8, 3, 3, 1};countingSort(arr);System.out.println("Sorted array: ");for (int i : arr) {System.out.print(i + " ");}}
}

桶排序:基于分桶的分布式排序算法

算法原理

桶排序(Bucket Sort)是一种分布式排序算法,适用于数据分布均匀的场景。其核心思想是将待排序的元素分到多个“桶”中,每个桶内部再使用其他排序算法(如插入排序)进行排序,最后将所有桶中的元素按顺序合并。

算法步骤

  1. 确定桶的数量,并将元素分配到对应的桶中。
  2. 对每个桶中的元素进行排序(通常使用插入排序)。
  3. 将所有桶中的元素按顺序合并。

时间复杂度与空间复杂度

  • 时间复杂度
    • 最坏情况:O(n²),当所有元素都被分配到同一个桶时。
    • 最好情况:O(n + k),当每个桶中只有一个元素时。
    • 平均情况:O(n + k),其中n是序列的长度,k是桶的数量。
  • 空间复杂度:O(n + k),需要额外的桶空间。

Java实现

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;public class BucketSort {public static void bucketSort(float[] arr) {if (arr == null || arr.length == 0) {return;}// 创建桶int n = arr.length;List<List<Float>> buckets = new ArrayList<>(n);for (int i = 0; i < n; i++) {buckets.add(new ArrayList<>());}// 将元素分配到桶中for (float num : arr) {int bucketIndex = (int) (n * num);buckets.get(bucketIndex).add(num);}// 对每个桶中的元素进行排序for (List<Float> bucket : buckets) {Collections.sort(bucket);}// 合并所有桶中的元素int index = 0;for (List<Float> bucket : buckets) {for (float num : bucket) {arr[index++] = num;}}}public static void main(String[] args) {float[] arr = {0.42f, 0.32f, 0.33f, 0.52f, 0.37f, 0.47f, 0.51f};bucketSort(arr);System.out.println("Sorted array: ");for (float i : arr) {System.out.print(i + " ");}}
}

基数排序:基于位数的稳定排序算法

算法原理

基数排序(Radix Sort)是一种稳定的排序算法,适用于整数或字符串的排序。其核心思想是按照元素的位数(从最低位到最高位)进行排序,每次排序都基于当前位数的值,最终得到有序序列。

算法步骤

  1. 确定待排序序列中最大数的位数。
  2. 从最低位开始,依次对每一位进行排序(通常使用计数排序)。
  3. 重复上述步骤,直到最高位。

时间复杂度与空间复杂度

  • 时间复杂度:O(d * (n + k)),其中n是序列的长度,d是最大数的位数,k是基数(如10进制为10)。
  • 空间复杂度:O(n + k),需要额外的计数数组和临时数组。

Java实现

public class RadixSort {public static void radixSort(int[] arr) {if (arr == null || arr.length == 0) {return;}// 找出最大值int max = arr[0];for (int num : arr) {if (num > max) max = num;}// 对每一位进行排序for (int exp = 1; max / exp > 0; exp *= 10) {countingSortByDigit(arr, exp);}}private static void countingSortByDigit(int[] arr, int exp) {int n = arr.length;int[] output = new int[n];int[] count = new int[10];// 统计每个数字出现的次数for (int num : arr) {int digit = (num / exp) % 10;count[digit]++;}// 计算累加次数for (int i = 1; i < 10; i++) {count[i] += count[i - 1];}// 根据计数数组重构排序后的数组for (int i = n - 1; i >= 0; i--) {int digit = (arr[i] / exp) % 10;output[count[digit] - 1] = arr[i];count[digit]--;}// 将排序结果复制回原数组System.arraycopy(output, 0, arr, 0, n);}public static void main(String[] args) {int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};radixSort(arr);System.out.println("Sorted array: ");for (int i : arr) {System.out.print(i + " ");}}
}

对比与总结

计数排序 vs 桶排序 vs 基数排序

特性计数排序桶排序基数排序
时间复杂度O(n + k)O(n + k)O(d * (n + k))
空间复杂度O(k)O(n + k)O(n + k)
稳定性稳定稳定稳定
适用场景整数范围较小数据分布均匀整数或字符串

选择与应用

  • 计数排序:适合整数范围已知且较小的场景。
  • 桶排序:适合数据分布均匀的场景,能够有效处理浮点数等数据。
  • 基数排序:适合整数或字符串的排序,尤其在位数较少的场景下表现优异。

通过对计数排序、桶排序和基数排序的讲解,我们可以看到这些非比较排序算法在特定场景下展现出了卓越的性能。希望这篇博客能为你揭示非比较排序的魅力,并为你的编程技能增添一份光彩。无论你是初学者还是经验丰富的开发者,掌握这些技巧都将有助于你在数据处理方面更加得心应手。


http://www.ppmy.cn/server/152829.html

相关文章

stm32引脚模式GPIO

问题引入 stm32f103定时器的引脚GPIO_MODE_OUTPUT_PP和GPIO_MODE_AF_PP有什么区别&#xff1f; 在STM32F103微控制器中&#xff0c;使用定时器时涉及到的GPIO配置主要有两种模式&#xff1a;GPIO_MODE_OUTPUT_PP和GPIO_MODE_AF_PP。这两种模式的主要区别在于它们的用途和工作…

重温设计模式--工厂模式(简单、工厂、抽象)

文章目录 工厂模式定义工厂模式通常可以细分为以下几种类型1、简单工厂模式&#xff08;Simple Factory Pattern&#xff09;2、工厂方法模式&#xff08;Factory Method Pattern&#xff09;3、抽象工厂模式&#xff08;Abstract Factory Pattern) UML 图1、简单工厂模式UML2、…

基于Spring Boot的个性化推荐外卖点餐系统

一、系统概述 该系统旨在为用户提供便捷、个性化的外卖点餐体验&#xff0c;同时为商家提供高效、智能的餐饮管理服务。通过利用Spring Boot框架的稳定性和可扩展性&#xff0c;系统实现了前后端分离的开发模式&#xff0c;支持多种设备和平台&#xff0c;确保用户在不同场景下…

RabbitMQ中的Topic模式

在现代分布式系统中&#xff0c;消息队列&#xff08;Message Queue&#xff09;是实现异步通信、解耦系统组件的重要工具。RabbitMQ 是一个广泛使用的开源消息代理&#xff0c;支持多种消息传递模式&#xff0c;其中 Topic 模式 是一种灵活且强大的模式&#xff0c;允许生产者…

一步一步写线程之十六线程的安全退出之二例程

一、说明 在一篇分析了多线程的安全退出的相关机制和方式&#xff0c;那么本篇就针对前一篇的相关的分析进行举例分析。因为有些方法实现的方法类似&#xff0c;可能就不一一重复列举了&#xff0c;相关的例程主要以在Linux上的运行为主。 二、实例 线程间的同步&#xff0c…

【后端面试总结】MySQL主从复制逻辑的技术介绍

MySQL主从复制逻辑的技术介绍 1. 基本概念 MySQL主从复制是一种数据库复制技术&#xff0c;用于将一个数据库服务器&#xff08;主服务器&#xff0c;Master&#xff09;上的数据更改同步到一个或多个其他数据库服务器&#xff08;从服务器&#xff0c;Slave&#xff09;上。…

open Feign服务抽取

open Feign虽然简化了远程调用&#xff0c;但是仍然存在着一些不太好的问题&#xff0c;这种问题并不是代码程序的问题&#xff0c;而是代码无法服用&#xff0c;无法构成一种编程的思维模式&#xff0c;如果一个服务需要多次被其他服务所引用并且服务数量很多的时候&#xff0…

【Canvas与仪表盘】铝圈蓝底汽车速度仪表盘(可用键盘按键调节速度值)

【速度调节方法】 W或上箭头加速&#xff0c;S或下箭头减速。 【成图】 120*120的png图标 大小图&#xff1a; 【代码】 <!DOCTYPE html> <html lang"utf-8"> <meta http-equiv"Content-Type" content"text/html; charsetutf-8&quo…