有效排序限定范围内整数栈的教程：计数排序优化-java教程-PHP中文网

有效排序限定范围内整数栈的教程：计数排序优化

碧海醫心

发布： 2025-07-17 19:02:13

原创

343人浏览过

有效排序限定范围内整数栈的教程：计数排序优化

本文将深入探讨如何高效地对一个栈进行排序，该栈仅包含特定范围内的整数（例如1到4）。原始方法虽然可行，但在效率和代码简洁性方面存在改进空间。本文将介绍一种基于计数排序的优化方案，并提供详细的实现步骤和代码示例。摘要如下：

本文旨在提供一种高效的排序算法，用于对包含特定范围内整数的栈进行排序。通过采用计数排序的思想，结合数组或哈希表实现频率统计，并避免冗余循环，从而达到线性时间复杂度的排序效果。同时，本文还强调了使用 Deque 接口替代 Stack 类的最佳实践。

计数排序原理

计数排序是一种非基于比较的排序算法，它通过统计每个不同数值在输入数组中出现的次数，然后根据这些计数来确定每个数值在输出数组中的位置。这种算法特别适用于已知数值范围且范围不大的情况。

针对栈排序的优化方案

针对栈中仅包含特定范围内整数的情况，我们可以利用计数排序的思想进行优化。主要步骤包括：

频率统计： 遍历栈，统计每个数值出现的次数。
排序并入栈： 按照数值范围从大到小（或从小到大）的顺序，将每个数值根据其出现次数重新入栈。

使用数组实现

以下是使用数组实现计数排序的 Java 代码示例：

import java.util.ArrayDeque;
import java.util.Deque;

public class StackSorter {

    public static Deque<Integer> sortStack(Deque<Integer> stack, int min, int max) {
        int[] freq = new int[max - min + 1]; // 频率数组

        // 步骤 1: 统计频率
        while (!stack.isEmpty()) {
            int next = stack.pop();
            if (next >= min && next <= max) {
                freq[next - min]++;
            }
        }

        // 步骤 2: 排序并入栈
        for (int i = freq.length - 1; i >= 0; i--) {
            while (freq[i] > 0) {
                stack.push(i + min);
                freq[i]--;
            }
        }

        return stack;
    }

    public static void main(String[] args) {
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(5);
        stack.push(3);
        stack.push(2);
        stack.push(1);
        stack.push(3);
        stack.push(5);
        stack.push(3);
        stack.push(1);
        stack.push(4);
        stack.push(7);

        Deque<Integer> sortedStack = sortStack(stack, 1, 4);

        System.out.println("Sorted Stack: " + sortedStack); // 输出排序后的栈
    }
}

登录后复制

代码解释：

简篇AI排版

AI排版工具，上传图文素材，秒出专业效果！

554

查看详情

sortStack(Deque<Integer> stack, int min, int max): 接受一个 Deque 栈和最小值、最大值作为参数，返回排序后的栈。
freq[]: 一个整数数组，用于存储每个数值的频率。索引 i 对应于数值 i + min。
第一个 while 循环：遍历栈，统计每个数值的频率。
第二个 for 循环：按照降序（从最大值到最小值）遍历频率数组，并将每个数值根据其频率入栈。

使用哈希表实现

以下是使用哈希表实现计数排序的 Java 代码示例：

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

public class StackSorter {

    public static Deque<Integer> sortStackWithHashMap(Deque<Integer> stack, int min, int max) {
        Map<Integer, Integer> freq = new HashMap<>(); // 频率哈希表

        // 步骤 1: 统计频率
        while (!stack.isEmpty()) {
            int next = stack.pop();
            if (next >= min && next <= max) {
                freq.merge(next, 1, Integer::sum);
            }
        }

        // 步骤 2: 排序并入栈
        for (int i = max; i >= min; i--) {
            if (freq.containsKey(i)) {
                int count = freq.get(i);
                while (count > 0) {
                    stack.push(i);
                    count--;
                }
            }
        }

        return stack;
    }

    public static void main(String[] args) {
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(5);
        stack.push(3);
        stack.push(2);
        stack.push(1);
        stack.push(3);
        stack.push(5);
        stack.push(3);
        stack.push(1);
        stack.push(4);
        stack.push(7);

        Deque<Integer> sortedStack = sortStackWithHashMap(stack, 1, 4);

        System.out.println("Sorted Stack: " + sortedStack); // 输出排序后的栈
    }
}

登录后复制

代码解释：

sortStackWithHashMap(Deque<Integer> stack, int min, int max): 接受一个 Deque 栈和最小值、最大值作为参数，返回排序后的栈。
freq: 一个哈希表，用于存储每个数值的频率。键是数值，值是该数值的频率。
freq.merge(next, 1, Integer::sum): 用于更新哈希表中数值的频率。
第二个 for 循环：按照降序（从最大值到最小值）遍历数值范围，并将每个数值根据其频率入栈。

时间复杂度分析

无论是使用数组还是哈希表，该算法的时间复杂度都是 O(n)，其中 n 是栈中元素的数量。这是因为我们需要遍历栈一次来统计频率，然后再次遍历数值范围（范围大小为常数）来将元素入栈。

空间复杂度分析

使用数组时，空间复杂度为 O(k)，其中 k 是数值的范围（max - min + 1）。
使用哈希表时，空间复杂度取决于实际出现的不同数值的数量。在最坏情况下，如果所有数值都不同，则空间复杂度为 O(n)。

注意事项与总结

选择数据结构： 如果数值范围较小且已知，则使用数组通常更有效率，因为数组的访问速度更快。如果数值范围较大或未知，则使用哈希表可能更合适。
Deque 替代 Stack： java.util.Stack 类是一个遗留类，建议使用 Deque 接口及其实现类（如 ArrayDeque）来代替。Deque 提供了更丰富的功能和更好的性能。
算法适用性： 这种优化方案特别适用于数值范围有限且已知的情况。对于一般的排序问题，可能需要考虑其他排序算法。

通过采用计数排序的思想，并结合适当的数据结构，可以高效地对包含特定范围内整数的栈进行排序。本文提供的代码示例和分析可以帮助读者理解和应用这种优化方案。

以上就是有效排序限定范围内整数栈的教程：计数排序优化的详细内容，更多请关注php中文网其它相关文章！