当前位置：首页 > article >正文

数据结构十大排序之（基数，计数，桶排）

article 2024/12/24 1:42:35

接上期：

数据结构十大排序之（冒泡，快排，并归）-CSDN博客

前言

排序算法是计算机科学中的经典问题之一，它不仅是许多算法和数据结构的基础，也是我们日常生活中不可或缺的一部分。无论是在数据分析、数据库管理、搜索引擎，还是在操作系统的任务调度中，排序算法都扮演着至关重要的角色。随着信息量的剧增，如何高效地对数据进行排序，成为了计算机科学研究和工程实践中不断探索的重要课题。

在众多的排序算法中，不同的算法各具特色，适用于不同的应用场景。对于数据量较小的情况，简单排序算法如冒泡排序、插入排序可能已经足够高效；但对于大规模数据的排序，我们通常需要依赖更为高效的算法，如快速排序、归并排序和堆排序等。与此同时，基于数据分布特点的非比较排序算法，如计数排序、桶排序和基数排序，也在一些特定场景下展现出了独特的优势。

本博客将详细介绍常见的三大非比较排序算法：堆排序、桶排序和基数排序。我们将从算法的原理、实现步骤、时间复杂度和空间复杂度等方面进行分析，帮助读者全面了解各种排序算法的优缺点，以及它们的适用场景。无论你是初学者还是经验丰富的开发者，希望这篇文章能为你提供深入的理解，并为你在实际工作中选择合适的排序算法提供参考。

接下来，我们将逐一讲解这些排序算法，探索它们的实现原理，并通过实例演示它们在实际应用中的表现。

6. 计数排序

计数排序（Counting Sort）是一种非比较型排序算法，它通过统计数组中每个元素出现的次数来直接计算出该元素在排序后的位置。计数排序的核心思想是利用额外的空间来记录每个元素的频次，然后通过这些频次来重构已排序的数组。因为它不通过比较元素大小来决定顺序，因此其时间复杂度与元素的值域范围有直接关系。

原理

计数排序的基本思想是：

统计频次：遍历输入数组，统计每个元素出现的次数，存储在一个计数数组中。
累积计数：根据计数数组，计算出每个元素的最终位置（即该元素应该放置在结果数组中的位置）。
重建排序结果：根据累积的计数数组，将元素按照顺序放入输出数组中。

算法步骤

确定最大值和最小值：首先找出输入数组中的最大值和最小值，基于这个范围来构建计数数组。
初始化计数数组：创建一个大小为 max - min + 1 的计数数组，用来记录每个值的出现次数。
统计元素频次：遍历输入数组，将每个元素出现的次数存入计数数组中。
累积计数：对计数数组进行累加，更新每个元素的累积计数，表示该元素应该放置在排序后数组中的位置。
构建排序结果：根据累积计数数组的值，重建排序后的数组。

    // 计数排序函数
    public static void countingSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return; // 如果数组为空或只有一个元素，直接返回
        }

        // 1. 找到数组中的最大值和最小值
        int min = arr[0], max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < min) min = arr[i];
            if (arr[i] > max) max = arr[i];
        }

        // 2. 创建计数数组
        // 计数数组的大小是 max - min + 1，因为需要存储所有在 min 和 max 之间的整数
        int[] count = new int[max - min + 1];

        // 3. 统计每个元素的出现次数
        for (int i = 0; i < arr.length; i++) {
            count[arr[i] - min]++; // 通过 arr[i] - min 将值映射到计数数组的索引位置
        }

        // 4. 修改计数数组，变成累计计数数组
        for (int i = 1; i < count.length; i++) {
            count[i] += count[i - 1]; // 每个位置存储的是小于或等于当前值的元素数量
        }

        // 5. 生成排序后的数组
        int[] sortedArr = new int[arr.length];
        for (int i = arr.length - 1; i >= 0; i--) { // 反向遍历保证稳定性
            int value = arr[i];
            sortedArr[count[value - min] - 1] = value;
            count[value - min]--; // 减少该值的计数
        }

        // 6. 将排序后的结果复制回原数组
        System.arraycopy(sortedArr, 0, arr, 0, arr.length);
    }

代码讲解

1. 处理空数组或单元素数组的情况：
if (arr == null || arr.length <= 1) {
    return; // 如果数组为空或只有一个元素，直接返回
}
这一步通过检查数组是否为空或仅包含一个元素来避免不必要的操作。空数组或单元素数组本身就是有序的，所以直接返回。

2. 找到数组中的最小值和最大值：
int min = arr[0], max = arr[0];
for (int i = 1; i < arr.length; i++) {
    if (arr[i] < min) min = arr[i];
    if (arr[i] > max) max = arr[i];
}
在计数排序中，计数数组的大小取决于数组中元素的最小值和最大值。因此，第一步是通过遍历数组找到最小值 min 和最大值 max。这个过程的时间复杂度是 O(n)，其中 n 是数组的长度。

3. 创建计数数组：
int[] count = new int[max - min + 1];
计数数组 count 的长度为 max - min + 1，因为要考虑到所有在 min 和 max 之间的整数。
例如，如果数组中的元素最小是 2，最大是 5，那么 count 数组的长度将为 5 - 2 + 1 = 4。

4. 统计每个元素的出现次数：
for (int i = 0; i < arr.length; i++) {
    count[arr[i] - min]++;  // 通过 arr[i] - min 将值映射到计数数组的索引位置
}
这里的关键是通过 arr[i] - min 将原数组中的元素映射到计数数组中的对应位置。例如，如果 min 是 2，那么 arr[i] - min 将会把值 2 映射到 count[0]，值 3 映射到 count[1]，依此类推。
这个步骤的时间复杂度是 O(n)，每次遍历原数组并对计数数组进行更新。

5. 修改计数数组，变成累计计数数组：
for (int i = 1; i < count.length; i++) {
    count[i] += count[i - 1];  // 每个位置存储的是小于或等于当前值的元素数量
}
这里将计数数组转换为累计计数数组，使得每个位置的值表示小于或等于该位置的元素的总数量。例如，如果 count[2] 的值是 3，表示数组中有 3 个元素小于或等于当前元素。
这个步骤的时间复杂度是 O(k)，其中 k 是计数数组的长度（即 max - min + 1）。

6. 生成排序后的数组：
int[] sortedArr = new int[arr.length];
for (int i = arr.length - 1; i >= 0; i--) {  // 反向遍历保证稳定性
    int value = arr[i];
    sortedArr[count[value - min] - 1] = value;
    count[value - min]--;  // 减少该值的计数
}
通过反向遍历原数组来确保排序的稳定性。反向遍历可以确保相同元素保持原来的相对顺序。
count[value - min] - 1 表示当前值应当放置的位置，count[value - min] 记录了该值出现的次数，然后减去 1，得到其在排序数组中的索引。
这个步骤的时间复杂度也是 O(n)，因为它需要遍历整个数组。

7. 将排序后的数组复制回原数组：
System.arraycopy(sortedArr, 0, arr, 0, arr.length);
最后将排序结果复制回原数组。这一步的时间复杂度是 O(n)。

静态展示

假设我们有一个数组 [4, 2, 2, 8, 3, 3, 1]，我们用计数排序对其进行排序：

初始化：
- 输入数组：[4, 2, 2, 8, 3, 3, 1]
- 找到最大值和最小值：max = 8，min = 1
- 创建计数数组 count，长度为 (8 - 1 + 1) = 8，初始值为全零：[0, 0, 0, 0, 0, 0, 0, 0]
统计频次：
- 4 发生 1 次，2 发生 2 次，8 发生 1 次，3 发生 2 次，1 发生 1 次。
- 计数数组变为：[1, 1, 2, 2, 1, 0, 0, 1]，表示：
  - 1 出现 1 次，2 出现 2 次，3 出现 2 次，4 出现 1 次，8 出现 1 次。
累积计数：
- 对计数数组进行累积，得到：[1, 2, 4, 6, 7, 7, 7, 8]。
  - 累积数组的意义是：arr[i] 在排序后应该放置的位置。
重建排序结果：
- 创建一个输出数组 output，初始值为全零：[0, 0, 0, 0, 0, 0, 0]。
- 按照计数数组的累积值，从原数组倒序填充 output 数组：
  - 1 放在位置 0：output = [1, 0, 0, 0, 0, 0, 0]
  - 2 放在位置 1：output = [1, 2, 0, 0, 0, 0, 0]
  - 2 放在位置 2：output = [1, 2, 2, 0, 0, 0, 0]
  - 3 放在位置 3：output = [1, 2, 2, 3, 0, 0, 0]
  - 3 放在位置 4：output = [1, 2, 2, 3, 3, 0, 0]
  - 4 放在位置 5：output = [1, 2, 2, 3, 3, 4, 0]
  - 8 放在位置 6：output = [1, 2, 2, 3, 3, 4, 8]
返回结果：
- 最终排序后的数组为：[1, 2, 2, 3, 3, 4, 8]

时间复杂度

时间复杂度：O(n + k)
- n 是输入数组的大小，k 是输入数据中的最大值和最小值之间的范围（即元素的值域大小）。
- 计数排序的时间复杂度主要由两部分组成：
  1. 统计频次：遍历输入数组，时间复杂度为 O(n)。
  2. 累积计数：对计数数组进行累加，时间复杂度为 O(k)。
  3. 重建排序结果：遍历数组，将数据放入输出数组，时间复杂度为 O(n)。
空间复杂度：O(n + k)
- 需要额外的空间来存储计数数组和输出数组。计数数组的空间复杂度为 O(k)，输出数组的空间复杂度为 O(n)。

稳定性

计数排序是稳定的。在处理相同元素时，计数排序不会改变它们的相对顺序。因为在构建输出数组时，我们是从原数组的后端开始填充的，确保相等的元素按照它们在原数组中的顺序排列。

优缺点

优点：

时间复杂度低：当数据范围不大时，计数排序的时间复杂度可以达到 O(n)，非常高效。
稳定排序：计数排序是稳定的，适合对需要保持相等元素相对顺序的场景。
适用于特定场景：对于一些特定场景，比如数据范围较小且整数值分布均匀时，计数排序是一种非常高效的排序算法。

缺点：

需要额外空间：计数排序需要使用额外的空间来存储计数数组，因此在内存占用方面比较高。
数据范围大时效率低：当元素的值域非常大（例如，排序的整数范围是 1 到 10^9）时，计数排序的空间复杂度会非常高，导致内存占用过多。
只能排序整数或离散数据：计数排序不能直接用于排序浮动数据类型或连续型数据，因为它需要知道数据的值域。

适用场景

数据范围较小且离散：例如，当排序的数据范围已知且相对较小（如 0 到 100 之间的整数），计数排序非常高效。
整数排序：计数排序专门用于排序整数，因此在处理整数数组时非常有用。
需要稳定排序的场景：计数排序是稳定排序，适合用于需要保留元素相对顺序的应用场景。

7. 桶排序

桶排序（Bucket Sort）是一种基于分布的排序算法，类似于计数排序。它通过将数据分散到若干个桶（buckets）中，然后对每个桶内的数据进行排序，最后将所有桶中的元素合并，得到一个有序的序列。桶排序特别适合用于分布均匀的浮点数排序。

算法原理

桶排序的基本思想是：

划分桶：将数据分配到多个桶中，每个桶内的数据范围相同。桶的数量和数据的分布是桶排序的关键。
对每个桶进行排序：可以使用其他排序算法（例如插入排序、快速排序等）对每个桶内的元素进行排序。
合并桶中的数据：将所有桶中的数据按顺序合并，最终得到排序后的结果。

算法步骤

确定桶的数量和范围：
- 根据数据的范围和分布，确定桶的数量和每个桶的大小。一般来说，桶的数量不应太多，否则会导致空桶，浪费空间；也不应太少，否则每个桶内的数据量过大，导致排序效率低。
分配数据到桶中：
- 遍历输入数组中的每个元素，将其放入对应的桶中。每个桶对应一个数据范围，可以通过元素值来确定其应该放入哪个桶。
对每个桶内的元素进行排序：
- 对每个桶内的元素进行排序，常见的方法有插入排序、快速排序等。桶内的元素数量一般较少，所以可以使用时间复杂度较高的插入排序。
合并所有桶：
- 将排好序的每个桶中的元素合并成一个最终的有序数组。

import java.util.ArrayList;
import java.util.Collections;

public class BucketSort {

    // 桶排序函数
    public static void bucketSort(float[] arr) {
        if (arr == null || arr.length <= 1) {
            return; // 如果数组为空或只有一个元素，直接返回
        }

        // 1. 创建桶数组
        int n = arr.length;
        ArrayList<Float>[] buckets = new ArrayList[n];

        // 2. 初始化桶
        for (int i = 0; i < n; i++) {
            buckets[i] = new ArrayList<>();
        }

        // 3. 将数据分配到桶中
        for (int i = 0; i < n; i++) {
            int bucketIndex = (int) (arr[i] * n); // 根据元素值和桶的数量来计算桶的索引
            buckets[bucketIndex].add(arr[i]);
        }

        // 4. 对每个桶进行排序
        for (int i = 0; i < n; i++) {
            Collections.sort(buckets[i]); // 使用 Java 的 Collections.sort 对每个桶内部进行排序
        }

        // 5. 将排序后的元素合并回原数组
        int index = 0;
        for (int i = 0; i < n; i++) {
            for (float num : buckets[i]) {
                arr[index++] = num;
            }
        }
    }

    // 测试桶排序
    public static void main(String[] args) {
        float[] arr = {0.42f, 0.32f, 0.23f, 0.52f, 0.43f, 0.52f};
        System.out.println("排序前：");
        for (float num : arr) {
            System.out.print(num + " ");
        }

        bucketSort(arr);

        System.out.println("\n排序后：");
        for (float num : arr) {
            System.out.print(num + " ");
        }
    }
}

代码讲解

1. 函数为空和输入检查
public static void bucketSort(float[] arr) {
    if (arr == null || arr.length <= 1) {
        return; // 如果数组为空或只有一个元素，直接返回
    }
输入参数：该函数接受一个浮点数数组 arr。
空数组或单元素数组：首先检查数组是否为空或仅包含一个元素。如果数组为空或只有一个元素，直接返回，因为数组已经是有序的，排序操作没有必要进行。

2. 创建桶数组
int n = arr.length;
ArrayList<Float>[] buckets = new ArrayList[n];
n 变量：n 是数组的长度，表示待排序的元素数量。
桶数组：buckets 是一个数组，长度为 n，用来存放 n 个桶（ArrayList<Float> 类型的桶）。每个桶将用于存放一个区间内的元素。

3. 初始化桶
for (int i = 0; i < n; i++) {
    buckets[i] = new ArrayList<>();
}
这段代码初始化了每个桶（ArrayList）。桶的数量是和原数组长度一样的，即 n 个桶，每个桶开始时为空的 ArrayList。

4. 将数据分配到桶中
for (int i = 0; i < n; i++) {
    int bucketIndex = (int) (arr[i] * n);  // 根据元素值和桶的数量来计算桶的索引
    buckets[bucketIndex].add(arr[i]);
}
桶索引计算：根据元素的值来计算每个元素应该放在哪个桶中。假设数组中的元素是浮点数且在 [0, 1) 范围内，arr[i] * n 可以将值映射到 [0, n) 的区间。通过 (int) 强制转换取整数部分，得到该元素应该放入的桶的索引。

例如：如果 arr[i] = 0.42，而 n = 5，那么 bucketIndex = (int) (0.42 * 5) = 2，表示该元素应该放入 buckets[2]。

如果数据的范围不是 [0, 1)，你可以根据数据的实际范围做适当的调整，来确保每个元素被正确地分配到合适的桶。

将元素放入桶：buckets[bucketIndex].add(arr[i]) 将元素添加到对应桶的 ArrayList 中。

5. 对每个桶内部进行排序
for (int i = 0; i < n; i++) {
    Collections.sort(buckets[i]);  // 使用 Java 的 Collections.sort 对每个桶内部进行排序
}
对每个桶进行排序：这里使用了 Java 标准库中的 Collections.sort 方法对每个桶中的元素进行排序。桶内部的元素数量通常较少，可以使用 插入排序 或 快速排序 等高效排序算法。由于 Java 的 Collections.sort 是基于 归并排序 或 快速排序（具体依赖于数据结构），其平均时间复杂度是 O(k log k)，其中 k 是每个桶中元素的数量。

注意：桶排序的效率受桶内数据分布的影响。如果每个桶内部元素较少且分布均匀，使用桶排序的效率非常高。

6. 将排序后的元素合并回原数组
int index = 0;
for (int i = 0; i < n; i++) {
    for (float num : buckets[i]) {
        arr[index++] = num;
    }
}
合并排序结果：所有桶内的元素已经排序完毕，现在将桶内排序后的元素依次放回原数组 arr 中。这个过程是通过 index 变量来追踪原数组中的位置，将每个桶中的元素顺序地复制到原数组。

外层循环遍历每个桶，内层循环遍历桶内的元素并将其放入原数组 arr 中。

静态展示

假设我们有一个数组 [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.48]，我们用桶排序对其进行排序：

找到最大值和最小值：
- 最小值：0.17
- 最大值：0.94
确定桶的数量：
- 假设我们选择 4 个桶（桶的数量可以根据实际情况调整）。
- 桶的大小为 (0.94 - 0.17) / 4 = 0.1925。
将元素分配到桶中：
- 第一个桶 [0.17, 0.21]，因为这两个数落在 [0, 0.1925) 范围内。
- 第二个桶 [0.39, 0.26]，落在 [0.1925, 0.385) 范围内。
- 第三个桶 [0.72, 0.48]，落在 [0.385, 0.5775) 范围内。
- 第四个桶 [0.78, 0.94]，落在 [0.5775, 0.77) 范围内。
对每个桶内的元素进行排序：
- 第一个桶 [0.17, 0.21] 排序后为 [0.17, 0.21]。
- 第二个桶 [0.39, 0.26] 排序后为 [0.26, 0.39]。
- 第三个桶 [0.72, 0.48] 排序后为 [0.48, 0.72]。
- 第四个桶 [0.78, 0.94] 排序后为 [0.78, 0.94]。
合并所有桶：
- 合并后的数组为 [0.17, 0.21, 0.26, 0.39, 0.48, 0.72, 0.78, 0.94]。

时间复杂度

最坏时间复杂度：O(n²)，当所有数据都集中在同一个桶中时，桶内的排序退化为排序整个数组，导致时间复杂度为 O(n²)。这通常发生在数据的分布极为不均匀时。
平均时间复杂度：O(n + k log k)，其中 n 是数据元素个数，k 是桶的数量。假设桶内元素分布均匀，且每个桶内排序时使用的是快速排序或插入排序，桶排序的时间复杂度为 O(n)（分配元素和合并），加上桶内排序的复杂度（k log k）。
空间复杂度：O(n + k)，其中 n 是输入数组的大小，k 是桶的数量。需要额外的空间来存储桶和排序后的输出数组。

稳定性

桶排序通常是稳定的，因为在桶内的排序是稳定的（如使用插入排序或其他稳定排序算法），并且在合并桶时保持了元素的相对顺序。

优缺点

优点：

高效：当数据均匀分布时，桶排序可以在线性时间内完成排序，时间复杂度为 O(n)。
稳定排序：桶排序是稳定的，能够保持相等元素的相对顺序。
适用特定数据分布：在数据分布均匀的情况下，桶排序的性能非常高。

缺点：

空间复杂度高：需要额外的空间来存储桶，尤其是当数据量较大时，可能会占用大量内存。
不适合大范围数据：当数据的范围很大但数据量较少时，桶排序的效果较差，因为桶的数量会过大，导致空桶占据大量空间。
对数据分布有要求：桶排序要求数据要均匀分布，否则性能可能不如预期。

适用场景

数据均匀分布的情况：桶排序适用于数据较为均匀分布的情况，例如排序浮点数或某些特定类型的整数。
当知道数据范围：桶排序适用于知道数据范围且数据范围较小的情况。特别是在排序大数据量的小范围数值时，桶排序非常高效。

8.基数排序

基数排序（Radix Sort）是一种非比较型排序算法，它通过将数据按位数（digit）进行排序，从最低位到最高位或从最高位到最低位，逐步完成排序。基数排序可以对整数或字符串等具有固定长度的元素进行排序，其核心思想是通过多次对数字的每一位进行排序，最终将数据整体排序。

基数排序特别适合于处理整数或字符串这类具有确定长度的对象，尤其是在数据范围相对较小的情况下，它可以比比较型排序算法（如快速排序、归并排序等）更高效。

算法原理

基数排序的基本思想是：

从最低位（或最高位）开始：首先按数字的最低位进行排序，然后按次低位排序，直到最高位。
按位数排序：对于每一位数字，使用稳定的排序算法（如计数排序）来排序数据。
逐步排序：重复上述步骤，直到所有位数的排序完成，最终得到一个有序的序列。

基数排序的步骤

选择一个基数：确定排序的基数（比如数字的位数）。对于整数来说，基数是数字的位数；对于字符串来说，基数是字符的长度。
按位排序：从最低位开始，对所有数据进行排序，然后逐步移动到高位，直到排序所有位。
稳定排序：每次对一位排序时，使用稳定的排序算法（例如计数排序），保证相同位数的元素不会改变相对顺序。

基数排序（Radix Sort）是一种非比较型排序算法，它通过对数字的每一位进行排序，逐步构建起有序序列。基数排序采用 LSD（Least Significant Digit） 或 MSD（Most Significant Digit） 方法，这里我们讨论常见的 LSD 方法，即从最低位（个位）开始排序，逐步处理到最高位（最高位）。

import java.util.Arrays;

public class RadixSort {

    // 基数排序的主要函数
    public static void radixSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return; // 如果数组为空或只有一个元素，直接返回
        }

        // 找出数组中的最大值，确定排序的最大位数
        int max = getMax(arr);

        // 从最低位开始，依次对每一位进行排序
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countingSortByDigit(arr, exp);
        }
    }

    // 计算数组中的最大值
    private static int getMax(int[] arr) {
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        return max;
    }

    // 对数组按某一位数（如个位、十位）进行排序
    private static void countingSortByDigit(int[] arr, int exp) {
        int n = arr.length;
        int[] output = new int[n]; // 输出数组
        int[] count = new int[10]; // 计数数组，用于存储0-9的数字出现次数

        // 存储每个数字的出现次数
        for (int i = 0; i < n; i++) {
            int digit = (arr[i] / exp) % 10; // 获取当前位的数字
            count[digit]++;
        }

        // 更新计数数组，count[i] 存储的是元素 <= i 的个数
        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};
        System.out.println("排序前：");
        System.out.println(Arrays.toString(arr));

        radixSort(arr);

        System.out.println("排序后：");
        System.out.println(Arrays.toString(arr));
    }
}。

代码讲解

1. radixSort 函数：主排序逻辑
public static void radixSort(int[] arr) {
    if (arr == null || arr.length <= 1) {
        return; // 如果数组为空或只有一个元素，直接返回
    }

    // 找出数组中的最大值，确定排序的最大位数
    int max = getMax(arr);

    // 从最低位开始，依次对每一位进行排序
    for (int exp = 1; max / exp > 0; exp *= 10) {
        countingSortByDigit(arr, exp);
    }
}
参数： int[] arr 是待排序的数组。

空数组或单元素数组检查： if (arr == null || arr.length <= 1) 检查数组是否为空或仅包含一个元素。如果是，直接返回，因为一个元素的数组已经是有序的。

获取最大值：

int max = getMax(arr); 获取数组中的最大值，以确定排序的最大位数。比如，数组中最大值为 802，则需要排序 3 次（个位、十位、百位）。

从最低位开始排序：

for (int exp = 1; max / exp > 0; exp *= 10) 是基数排序的核心。exp 是当前正在排序的位数（个位、十位、百位等）。exp 从 1 开始，表示最低位（个位），然后依次乘以 10，处理更高位（十位、百位等）。
max / exp > 0 这一条件确保了我们对所有位进行排序，直到最大值的最高位处理完成。

对每一位进行排序：

每次根据当前位的数字调用 countingSortByDigit(arr, exp) 对数组进行排序。

2. getMax 函数：获取数组中的最大值
private static int getMax(int[] arr) {
    int max = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    return max;
}
该函数遍历数组，找出数组中的最大值。最大值用于确定需要处理多少位数字（即最大值的位数决定了排序的次数）。
时间复杂度： O(n)，其中 n 是数组的长度。

3. countingSortByDigit 函数：按位排序
private static void countingSortByDigit(int[] arr, int exp) {
    int n = arr.length;
    int[] output = new int[n]; // 输出数组
    int[] count = new int[10]; // 计数数组，用于存储0-9的数字出现次数

    // 存储每个数字的出现次数
    for (int i = 0; i < n; i++) {
        int digit = (arr[i] / exp) % 10; // 获取当前位的数字
        count[digit]++;
    }

    // 更新计数数组，count[i] 存储的是元素 <= i 的个数
    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);
}
这个函数对数组 arr 按照指定的位数（exp）进行排序。

关键步骤解释：

计算每个数字在当前位上的频率：

int digit = (arr[i] / exp) % 10; 通过 exp 计算每个数字在当前位上的值。
例如，当 exp = 10 时，处理的是十位数字，arr[i] / 10 获取十位数字，% 10 取得该位的具体数字。

更新计数数组：

int[] count = new int[10]; 计数数组的大小为 10，用于统计每个数字（0-9）在当前位上的出现次数。
for (int i = 0; i < n; i++) { count[digit]++; } 遍历数组，统计每个数字在当前位上的出现次数。

更新计数数组，使其存储位置：

for (int i = 1; i < 10; i++) { count[i] += count[i - 1]; } 累加计数数组中的每个元素，使得 count[i] 存储的是小于等于 i 的数字的个数。
这个步骤保证了排序的稳定性（同样的数字在排序时不会交换位置）。

根据当前位数字的计数填充输出数组：

for (int i = n - 1; i >= 0; i--) { ... } 逆序遍历原数组，以保证排序的稳定性（如果按正常顺序填充，可能会改变相同数字的相对顺序）。
output[count[digit] - 1] = arr[i]; 将当前数字放入 output 数组的正确位置，count[digit]-- 更新计数。

将排序后的结果复制回原数组：

System.arraycopy(output, 0, arr, 0, n); 将排序后的数组 output 复制回原数组 arr。

静态展示

假设我们有一个整数数组 [170, 45, 75, 90, 802, 24, 2, 66]，我们使用基数排序进行排序：

第一次按个位排序：
- 输入数组：[170, 45, 75, 90, 802, 24, 2, 66]
- 个位数：[0, 5, 5, 0, 2, 4, 2, 6]，排序后为：[170, 90, 802, 2, 45, 75, 24, 66]
第二次按十位排序：
- 输入数组：[170, 90, 802, 2, 45, 75, 24, 66]
- 十位数：[7, 9, 0, 0, 4, 7, 2, 6]，排序后为：[802, 2, 24, 45, 66, 75, 170, 90]
第三次按百位排序：
- 输入数组：[802, 2, 24, 45, 66, 75, 170, 90]
- 百位数：[8, 0, 0, 0, 0, 0, 1, 0]，排序后为：[2, 24, 45, 66, 75, 90, 170, 802]

最终，排序结果为：[2, 24, 45, 66, 75, 90, 170, 802]。

时间复杂度

最坏时间复杂度：O(n * k)
- 其中 n 是数组的元素数量，k 是元素的最大位数（对于整数来说，k 是数字的位数）。
- 每一轮排序需要 O(n) 的时间进行桶排序（或计数排序），最多进行 k 次排序，因此时间复杂度为 O(n * k)。
空间复杂度：O(n + k)
- 需要额外的空间来存储每个数字在各个位数的排序结果，空间复杂度是 O(n)，以及计数数组的大小是 O(k)，因此总空间复杂度是 O(n + k)。

稳定性

基数排序是稳定的，因为每次排序时使用的是稳定的排序算法（如计数排序）。即使是具有相同当前位数字的元素，它们在排序后仍然保持相对顺序不变。

优缺点

优点：

线性时间复杂度：在某些情况下，基数排序的时间复杂度接近 O(n)，尤其是数据位数较少时。
适用于大规模数据：对于具有固定长度的整数或字符串，基数排序比传统的比较型排序更高效，尤其是当数据范围较大时。
稳定排序：基数排序是稳定的，适合需要保持元素相对顺序的应用。

缺点：

空间复杂度较高：基数排序需要额外的空间来存储中间结果，特别是在排序大范围的数字时，可能会占用较多的内存。
不适用于所有数据类型：基数排序通常只适用于整数或字符串，对于浮点数或其他复杂数据类型，基数排序并不直接适用。
依赖数据的位数：基数排序的性能与数据的位数（或字符串的长度）直接相关。如果数据位数较多，基数排序的效率可能会降低。

适用场景

基数排序适用于以下场景：

整数排序：特别是当整数的位数较少时，基数排序可以非常高效。
固定长度字符串排序：基数排序也可以用于排序长度相同的字符串，如按字典顺序排序字符串。
大规模数据：基数排序适用于大规模数据的排序，尤其是当数据的范围有限且数据位数不多时。

9. 排序算法复杂度及稳定性分析

10 总结：

1. 冒泡排序（Bubble Sort）

优点：

简单易懂：实现起来非常简单，容易理解和编写代码。
空间复杂度低：只需要常数空间 O(1)，是原地排序。

缺点：

效率低：最坏情况下时间复杂度为 O(n²)，适用于数据量小的情况。即使在最优情况下（已排序），仍需要 O(n) 的时间来确认。
交换次数多：在大多数情况下，涉及较多的交换操作，降低了效率。

使用场景：

数据量小：适用于小规模数据的排序，或者数据几乎已经排序好的场景。
教学用途：因为其实现简单，常作为学习排序算法的入门例子。

2. 选择排序（Selection Sort）

优点：

简单易懂：实现起来简单。
空间复杂度低：只需要 O(1) 的额外空间，是原地排序。
交换次数较少：相比冒泡排序，选择排序的交换次数较少。

缺点：

效率低：最坏情况下时间复杂度为 O(n²)，性能在数据量较大时非常差。
不稳定：在排序过程中，相同元素的相对位置可能发生改变。

使用场景：

数据量小：适用于小规模数据的排序。
空间受限：适合在内存空间非常有限的情况下使用。

3. 插入排序（Insertion Sort）

优点：

简单高效：对于已经部分排序的数据，插入排序非常高效，时间复杂度为 O(n)。
稳定排序：相同元素的相对位置不会改变。
空间复杂度低：只需要 O(1) 的额外空间，是原地排序。

缺点：

效率低：最坏情况下时间复杂度为 O(n²)，适用于数据量较小的情况。
对逆序数据无效：当数据几乎是逆序时，效率会较差。

使用场景：

小规模数据：适用于小规模数据或者几乎已排序的数据。
在线排序：适合实时或增量式数据排序，例如在线编辑器、实时数据输入等场景。

4. 快速排序（Quick Sort）

优点：

平均性能优秀：平均时间复杂度为 O(n log n)，是非常高效的排序算法。
原地排序：不需要额外的存储空间，空间复杂度为 O(log n)。
适应性强：对大多数数据集表现良好，尤其是数据随机分布时。

缺点：

最坏时间复杂度差：最坏情况下时间复杂度为 O(n²)，当数据几乎已排序或逆序时表现不佳。
不稳定排序：相同元素的相对顺序可能会发生改变。
递归开销大：当递归层数过多时，可能会导致栈溢出。

使用场景：

大规模数据：适合数据量大的情况，尤其是当数据分布较随机时。
需要较小的空间：需要在原地排序时使用。

5. 归并排序（Merge Sort）

优点：

稳定排序：保证相同元素的相对位置不变。
最坏情况性能好：时间复杂度始终为 O(n log n)，适用于任何数据集。
外部排序：可以用于大规模数据集的外部排序，适合内存不足的场景。

缺点：

空间复杂度高：需要额外的 O(n) 空间进行合并操作，不是原地排序。
合并操作较慢：需要不断地进行合并，增加了操作开销。

使用场景：

大规模数据：适用于对大规模数据进行排序，尤其是数据集无法完全加载进内存的情况。
稳定性要求高的场景：需要保证相同元素顺序不变的情况下使用。

6. 堆排序（Heap Sort）

优点：

时间复杂度 O(n log n)：在最坏情况下时间复杂度为 O(n log n)，比快速排序更加稳定。
原地排序：不需要额外空间，空间复杂度为 O(1)。
不依赖于数据分布：性能不受数据分布的影响。

缺点：

不稳定排序：相同元素的相对位置可能会发生变化。
常数因素较大：虽然时间复杂度是 O(n log n)，但相比于快速排序，其常数因素较大，实际运行速度可能较慢。
堆构建开销较大：堆构建的过程需要 O(n) 的时间。

使用场景：

需要稳定时间复杂度：适用于数据量较大的排序，且需要避免最坏情况的性能瓶颈。
内存空间受限：适合内存有限的情况下使用，因为堆排序是原地排序。

7. 计数排序（Counting Sort）

优点：

时间复杂度 O(n + k)：对于整数范围较小的数据，计数排序能够实现非常高效的排序，时间复杂度接近线性。
稳定排序：相同元素的顺序不会改变。
非常快速：特别适合处理整数或有限范围的元素。

缺点：

适用范围有限：只能用于整数或具有有限范围的数值数据，且范围过大时空间复杂度会很高。
不适用于浮点数和大范围数据：不能直接应用于浮点数排序或大范围的数值排序。

使用场景：

数值范围小：适用于数据范围较小且数据量较大的情况，如计数、频率统计等。
非比较排序：当数据是整数或符号时，计数排序可以提供线性时间复杂度。

8. 桶排序（Bucket Sort）

优点：

时间复杂度 O(n + k)：对于数据均匀分布的情况，桶排序能够非常高效地完成排序。
稳定排序：通过对每个桶内的数据进行排序，保证了排序的稳定性。

缺点：

空间复杂度高：需要额外的桶空间来存储数据，空间复杂度为 O(n)。
数据分布要求高：只有当数据均匀分布时，桶排序才具有优势，且不适用于大范围数据。

使用场景：

数据均匀分布的场景：适用于数据均匀分布且范围有限的情况，如浮点数排序。
大数据集：当数据量极大且数据分布较均匀时，桶排序是一个高效的选择。

9. 基数排序（Radix Sort）

优点：

时间复杂度 O(n * k)：基数排序在适当的条件下，可以接近线性时间复杂度。
稳定排序：保证相同元素的顺序不变。
适用于大数据集：特别适合于对大规模、固定长度的数字或字符串进行排序。

缺点：

空间复杂度高：需要额外的空间来存储每一位的排序结果。
仅适用于整数或字符串：不适用于浮点数排序或其他复杂数据类型。

使用场景：

整数和字符串排序：适用于整数或固定长度字符串的排序，特别是当数据位数较小且范围有限时。
大数据集排序：适合用于大规模数据的排序，尤其是当数据位数较少时。

10. 快速排序（Quick Sort）

优点：

时间复杂度 O(n log n)：平均情况下非常高效，是常见的排序算法之一。
原地排序：不需要额外的存储空间，空间复杂度为 O(log n)。
适应性强：对随机分布的数据非常高效。

缺点：

最坏情况 O(n²)：当数据已经近乎排序时，快速排序的性能会退化为 O(n²)。
不稳定排序：相同元素的顺序可能会改变。

使用场景：

大规模数据：当数据量大且数据分布随机时，快速排序非常高效。
时间敏感场景：在需要快速排序且内存占用较小的情况下使用。

结语：

排序算法作为计算机科学中最基础且最常用的算法之一，贯穿于各类应用程序和系统的设计中。从简单的冒泡排序到高效的快速排序和堆排序，从适用于特定数据类型的计数排序、桶排序到基数排序，每种排序算法都有其独特的优缺点和适用场景。

通过对十大排序算法的分析与对比，我们可以看到，不同的排序方法并非一成不变，而是根据数据的大小、数据的分布特点以及对空间和时间复杂度的要求来选择最合适的算法。在实际应用中，了解每种算法的时间复杂度、空间复杂度和稳定性，能够帮助我们在实际项目中做出明智的决策，选择最适合的排序方法。

虽然像快速排序和归并排序这样的比较型排序算法在大多数情况下表现优异，但在特定的场景下，如数据范围小或对稳定性有较高要求时，非比较排序算法如计数排序、桶排序和基数排序可能会带来显著的性能提升。

总之，排序算法不仅仅是一个学术课题，它在实际工作中也有着广泛的应用。掌握不同排序算法的优缺点和适用场景，不仅有助于提升我们解决问题的能力，也能使我们在面对复杂的数据处理任务时，做出更加高效且合理的选择。希望本文的总结能够为你深入理解排序算法的多样性与复杂性提供帮助，带你在算法的世界中走得更远。

无论你是学习算法的初学者，还是经验丰富的软件工程师，掌握这些排序算法将为你在编程和优化中提供强有力的工具。

查看全文

http://www.kler.cn/a/448667.html

【工具】通过js获取chrome浏览器扩展程序列表id及名称等

Redisson锁简单使用

Vue Web开发（十）

使用 Buildroot 构建带有 Avahi 支持的 Linux 系统

Linux之磁盘管理相关命令

ExcelVBA编程输出ColorIndex与对应颜色色谱

【计算机视觉】超简单！傅里叶变换的经典案例

Qt有哪些读取文件的方式

UE5 小怪血条

34 Opencv 自定义角点检测

Unity Apple Vision Pro 开发教程：物体识别跟踪

力扣 429 场周赛-前两题

Linux IPC：读写锁汇总整理

linux 合并uboot dtb kernel rootfs 文件制作nor flash 烧录镜像

通过移除 -march=native 解决 Ubuntu 20.04 程序运行“段错误 (核心已转储)”问题的详解

TIDB的备份与恢复、上传OSS

制作自己的Manjaro Linux Live DVD 光盘镜像

WebRTC服务质量（06）- 重传机制（03) NACK找到真正的丢包

Linux之压缩解压相关命令

网上球鞋竞拍系统｜Java｜SSM｜VUE｜前后端分离

MVCC了解

2024 高级爬虫笔记（四）协程、selenium

11爬虫：使用requests和selenium分别抓取4399网页游戏名称

LeetCode 35. 搜索插入位置 (C++实现)

12.18 web后端开发——数据库

【代码随想录】刷题记录(61)-二叉搜索树中的众数

接上期：

前言

6. 计数排序

原理

算法步骤

代码讲解

静态展示

时间复杂度

稳定性

优缺点

适用场景

7. 桶排序

算法原理

算法步骤

代码讲解

静态展示

时间复杂度

稳定性

优缺点

适用场景

8.基数排序

算法原理

基数排序的步骤

代码讲解

静态展示

时间复杂度

稳定性

优缺点

适用场景

9. 排序算法复杂度及稳定性分析

10 总结：

1. 冒泡排序（Bubble Sort）

优点：

缺点：

使用场景：

2. 选择排序（Selection Sort）

优点：

缺点：

使用场景：

3. 插入排序（Insertion Sort）

优点：

缺点：

使用场景：

4. 快速排序（Quick Sort）

优点：

缺点：

使用场景：

5. 归并排序（Merge Sort）

优点：

缺点：

使用场景：

6. 堆排序（Heap Sort）

优点：

缺点：

使用场景：

7. 计数排序（Counting Sort）

优点：

缺点：

使用场景：

8. 桶排序（Bucket Sort）

优点：

缺点：

使用场景：

9. 基数排序（Radix Sort）

优点：

缺点：

使用场景：

10. 快速排序（Quick Sort）

优点：

缺点：

使用场景：

结语：

相关文章：