使用计数排序优化栈内特定范围整数的排序_技术教程

本文针对对包含20个整数的栈进行排序，仅保留1到4范围内升序排列的值这一问题，提出了一种基于计数排序的优化方案。通过使用数组或HashMap统计各数值的频率，并按降序将数值重新压入栈中，实现了线性时间复杂度的排序。同时，强调了在Java中优先使用Deque接口的实现类代替Stack类的最佳实践。

问题背景

对栈中的特定范围内的整数进行排序，并在性能上进行优化是一个常见的算法问题。初始方案虽然能够解决问题，但在时间和空间复杂度上存在改进空间。本文将介绍如何利用计数排序算法，以更高效的方式解决这一问题。

计数排序算法详解

计数排序是一种非基于比较的排序算法，它通过统计每个元素出现的次数来确定排序后的位置。由于问题限定了排序范围为1到4，因此非常适合使用计数排序。

算法步骤：

统计频率： 遍历栈中的每个元素，统计1到4每个数字出现的次数。
重新压栈： 按照4、3、2、1的顺序，将对应数字压入栈中，压入的次数等于该数字的频率。

代码示例（使用数组）：

import java.util.Stack;

public class StackSorter {

    public static Stack sortStack(Stack 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 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 sortedStack = sortStack(stack);

        System.out.println("Sorted Stack: " + sortedStack); // 输出：Sorted Stack: [4, 3, 3, 3, 2, 1, 1]
    }
}

代码示例（使用HashMap）：

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

public class StackSorter {

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

        Map 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 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 sortedStack = sortStack(stack);

        System.out.println("Sorted Stack: " + sortedStack); // 输出：Sorted Stack: [4, 3, 3, 3, 2, 1, 1]
    }
}

时间和空间复杂度分析

时间复杂度： 线性时间复杂度O(n)，其中n是栈中元素的数量。算法只需要遍历栈一次进行频率统计，再遍历频率数组或HashMap一次进行重新压栈。
空间复杂度： O(k)，其中k是排序范围的大小（在本例中k=4）。需要额外的空间来存储频率统计信息，可以使用数组或HashMap。

最佳实践：使用Deque接口

在Java中，java.util.Stack是一个遗留类，官方建议使用Deque接口及其实现类（如ArrayDeque或LinkedList）来代替Stack。

示例：

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

public class StackSorter {

    public static Deque sortStack(Deque 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) {
        Deque 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 sortedStack = sortStack(stack);

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