基于计数排序优化栈内特定范围整数的排序-java教程-PHP中文网

基于计数排序优化栈内特定范围整数的排序

碧海醫心

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

原创

193人浏览过

基于计数排序优化栈内特定范围整数的排序

摘要：本文针对栈内特定范围（1-4）的整数排序问题，提出了一种基于计数排序的优化方案。通过使用数组或HashMap统计各数值的出现频率，避免了传统排序算法的比较操作，实现了线性时间复杂度的排序。同时，本文还提供了Java代码示例，并讨论了使用Deque替代Stack的建议，旨在帮助读者理解和应用计数排序算法，提高栈排序的效率。

在处理栈数据结构时，对特定范围内的整数进行排序是一个常见的需求。传统的排序算法，如快速排序，虽然通用性强，但在面对特定范围的数据时，并非最优选择。本文将介绍一种更高效的解决方案：计数排序，并结合Java代码示例，详细阐述其原理和实现。

计数排序原理

计数排序是一种非比较型整数排序算法，其核心思想是统计每个元素出现的次数，然后根据元素值的大小，依次将元素放回原序列。对于已知范围的整数排序，计数排序具有线性时间复杂度O(n)的优势。

序列猴子开放平台

具有长序列、多模态、单模型、大数据等特点的超大规模语言模型

查看详情

算法步骤

统计频率： 遍历栈中的元素，统计每个元素出现的次数。可以使用数组或HashMap来存储频率信息。
重建栈： 按照元素值的大小，依次将元素放回栈中。每个元素放回的次数等于其出现的频率。

Java代码实现（数组）

import java.util.Stack;

public class StackSort {

    public static Stack<Integer> sortStack(Stack<Integer> stack) {
        final int min = 1;
        final int max = 4;

        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) {
        Stack<Integer> stack = new Stack<>();
        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);

        Stack<Integer> sortedStack = sortStack(stack);

        System.out.println("Sorted Stack: " + sortedStack);
    }
}

登录后复制

Java代码实现（HashMap）

import java.util.Stack;
import java.util.HashMap;
import java.util.Map;

public class StackSort {

    public static Stack<Integer> sortStack(Stack<Integer> stack) {
        final int min = 1;
        final int max = 4;

        Map<Integer, Integer> freq = new HashMap<>(); // 频率Map

        // 步骤 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) {
        Stack<Integer> stack = new Stack<>();
        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);

        Stack<Integer> sortedStack = sortStack(stack);

        System.out.println("Sorted Stack: " + sortedStack);
    }
}

登录后复制

空间复杂度

数组实现: 空间复杂度为 O(k)，其中 k 是整数的范围（在本例中为 4 - 1 + 1 = 4）。
HashMap实现: 最坏情况下，如果栈中包含所有范围内的整数，空间复杂度也为 O(k)。

注意事项

数据范围： 计数排序适用于已知数据范围且范围不大的情况。如果数据范围过大，会导致空间复杂度过高。
稳定性： 计数排序是一种稳定的排序算法，即相等元素的相对顺序不会改变。
java.util.Stack的替代方案： 官方文档建议使用Deque接口的实现类（如ArrayDeque或LinkedList）来替代java.util.Stack，因为Stack类是遗留类，在性能和功能上不如Deque。

使用Deque替代Stack

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

public class StackSort {

    public static Deque<Integer> sortStack(Deque<Integer> stack) {
        final int min = 1;
        final int max = 4;

        Map<Integer, Integer> freq = new HashMap<>(); // 频率Map

        // 步骤 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 = sortStack(stack);

        System.out.println("Sorted Stack: " + sortedStack);
    }
}

登录后复制

总结

计数排序是一种高效的整数排序算法，特别适用于已知范围且范围不大的数据。通过统计元素频率，避免了比较操作，实现了线性时间复杂度。在Java中，可以使用数组或HashMap来实现计数排序。同时，建议使用Deque接口的实现类来替代java.util.Stack，以获得更好的性能和功能。在实际应用中，应根据具体情况选择合适的排序算法。当数据范围较大时，可以考虑使用其他排序算法，如归并排序或快速排序。

以上就是基于计数排序优化栈内特定范围整数的排序的详细内容，更多请关注php中文网其它相关文章！