本文探讨了如何在给定栈中，高效地对特定范围（1-4）内的整数进行排序，并保持升序。通过应用计数排序（Counting sort）算法，我们实现了线性时间复杂度O(N)的解决方案，避免了传统比较排序的局限性，并优化了空间使用，确保了算法的简洁性和高性能。
引言：问题背景与挑战
在处理数据结构中的排序问题时，我们经常面临各种约束。一个典型场景是：给定一个包含20个整数的栈，要求对其进行排序，但只保留其中值在1到4范围内的整数，并使这些保留下来的整数最终在栈中按升序排列。此外，操作限制是每次只能移动一个值。
传统的比较排序算法（如快速排序、归并排序）通常适用于通用场景，但在面对特定值范围和数据结构限制时，可能无法达到最优效率。对于本问题，由于待排序的数值范围非常小且固定（1到4），这为采用非比较型排序算法提供了机会，从而实现更高的性能。
计数排序（Counting Sort）原理
计数排序是一种非比较型排序算法，其核心思想是统计数组中每个元素出现的次数，然后根据这些计数信息将元素放置到正确的位置。它特别适用于整数排序，尤其当整数的取值范围（K）相对较小或与元素总数（N）相近时，能展现出优于比较排序的性能。
对于本问题，我们不需要传统的计数排序中计算累积频率的步骤，因为我们不是要将所有元素排序到一个新数组中，而是要将特定范围内的元素重新组织到原始栈中。算法的核心在于两个阶段：频率统计和栈重建。
针对栈排序的优化算法步骤
考虑到问题的特定需求（只保留1-4范围内的值，并按升序排列），我们可以对计数排序进行优化。
步骤一：构建频率直方图
此阶段的目标是遍历原始栈，统计在目标范围 [1, 4] 内的每个整数出现的频率。
- 初始化频率存储： 创建一个数组（或哈希表）来存储每个目标整数的出现次数。由于目标范围是1到4，一个大小为 max – min + 1 的整型数组是最佳选择，其中 min 为1，max 为4。数组的索引可以直接映射到对应的数值（通过简单的偏移）。
- 遍历并统计： 从栈中逐个弹出元素。对于每个弹出的元素，检查它是否在 [1, 4] 的范围内。如果符合，则将其对应的频率计数加一。超出此范围的元素将被忽略，从而实现过滤。
示例： 如果栈中包含 [5, 3, 2, 1, 3, 5, 3, 1, 4, 7]，经过此步骤后，频率直方图可能为：
- 1: 2次
- 2: 1次
- 3: 3次
- 4: 1次
步骤二：按序重建栈
此阶段的目标是根据频率直方图，将符合条件的整数按升序重新推入栈中。由于栈的特性是“后进先出”（LIFO），为了使最终栈底部是1、顶部是4（即从栈顶到栈底是4,3,2,1），我们需要从最大值开始逆序推入。
- 逆序遍历频率： 从目标范围的最大值（4）开始，向下遍历到最小值（1）。
- 重复推入： 对于当前遍历到的每个值 i，根据其在频率直方图中记录的次数，重复将 i 推入栈中，直到该值的计数为零。
通过这种逆序推入的方式，当所有元素都推入完成后，栈的底部将是所有的1，接着是2，然后是3，最后顶部是4。这样，当从栈中弹出元素时，它们将按1, 2, 3, 4的升序出现。
代码实现示例
以下是使用Java语言实现上述优化计数排序的示例代码。我们推荐使用数组作为频率直方图，因为它在固定小范围整数场景下性能更优且更直观。
import java.util.ArrayDeque; import java.util.Deque; import java.util.HashMap; import java.util.Map; public class StackSorter { /** * 使用数组实现计数排序，对栈中特定范围的整数进行排序。 * 推荐使用 ArrayDeque 代替 legacy 的 java.util.Stack。 * * @param stack 待排序的栈 * @param min 目标范围的最小值 * @param max 目标范围的最大值 * @return 排序后的栈，只包含指定范围内的元素，且按升序排列（栈底到栈顶） */ public static Deque<Integer> sortStackWithCountingSort(Deque<Integer> stack, int min, int max) { // 步骤一：构建频率直方图 // freq 数组的索引对应 (值 - min)，例如 freq[0] 存储 min 的频率 int[] freq = new int[max - min + 1]; while (!stack.isEmpty()) { int next = stack.pop(); // 弹出栈顶元素 // 检查元素是否在目标范围内 if (next >= min && next <= max) { freq[next - min]++; // 对应值的频率加一 } } // 步骤二：按序重建栈 // 从目标范围的最大值开始，逆序推入，以确保栈底是最小值，栈顶是最大值 for (int i = freq.length - 1; i >= 0; i--) { int valueToPush = i + min; // 将索引转换回实际值 while (freq[i] > 0) { stack.push(valueToPush); // 推入元素 freq[i]--; // 对应频率减一 } } return stack; } /** * 另一种实现方式：使用 HashMap 作为频率存储。 * 功能相同，但对于小范围整数，数组通常更高效。 */ public static Deque<Integer> sortStackWithCountingSortHashMap(Deque<Integer> stack, int min, int max) { Map<Integer, Integer> freqMap = new HashMap<>(); while (!stack.isEmpty()) { int next = stack.pop(); if (next >= min && next <= max) { freqMap.merge(next, 1, Integer::sum); // 计算频率 } } for (int i = max; i >= min; i--) { int count = freqMap.getOrDefault(i, 0); // 获取频率，若无则为0 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); System.out.println("Original Stack (top to bottom): " + stack); // 使用数组实现的计数排序 Deque<Integer> sortedStackArray = sortStackWithCountingSort(stack, 1, 4); System.out.println("Sorted Stack (Array Impl, top to bottom): " + sortedStackArray); // 验证排序结果（从栈顶弹出） System.out.print("Popping elements (Array Impl): "); while (!sortedStackArray.isEmpty()) { System.out.print(sortedStackArray.pop() + " "); } System.out.println("n"); // 重置栈用于HashMap示例 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); // 使用HashMap实现的计数排序 Deque<Integer> sortedStackHashMap = sortStackWithCountingSortHashMap(stack, 1, 4); System.out.println("Sorted Stack (HashMap Impl, top to bottom): " + sortedStackHashMap); // 验证排序结果（从栈顶弹出） System.out.print("Popping elements (HashMap Impl): "); while (!sortedStackHashMap.isEmpty()) { System.out.print(sortedStackHashMap.pop() + " "); } System.out.println(); } }
算法复杂度分析
-
时间复杂度：
- 步骤一（构建频率直方图）： 需要遍历原始栈中的所有N个元素。对于每个元素，进行常数时间的操作（弹出、范围检查、数组/HashMap更新）。因此，此步骤的时间复杂度为O(N)。
- 步骤二（按序重建栈）： 需要遍历目标值范围K次（从max到min），并在每个值上重复推入其频率次数。总的推入操作次数等于保留下来的元素总数（最多N个）。因此，此步骤的时间复杂度为O(K + N’)，其中N’是保留下来的元素数量。
- 总时间复杂度： O(N + K)。由于本问题中K（范围大小，即4）是一个常数，因此总时间复杂度可以简化为 O(N)，即线性时间复杂度。这比任何基于比较的排序算法（通常为O(N log N)）都要高效。
-
空间复杂度：
- 频率直方图： 需要一个大小为 max – min + 1 的数组或HashMap来存储频率。由于 max – min + 1 也是一个常数（4），因此额外空间复杂度为 O(K)，可以视为 O(1)，即常数空间复杂度。
注意事项与最佳实践
- java.util.Stack 的弃用： 在Java中，java.util.Stack 类是历史遗留类，不推荐在新代码中使用。它继承自 Vector，是一个同步的、基于数组的列表，其API设计并不完全符合栈的抽象。更推荐的做法是使用 Deque 接口的实现类，如 ArrayDeque 或 LinkedList，它们提供了更高效且符合栈操作的 push(), pop(), peek() 方法。本教程中的代码示例已采用 ArrayDeque。
- “每次只能移动一个值”的遵守： 计数排序算法通过逐个弹出栈元素进行频率统计，然后逐个推入元素进行栈重建，完全符合“每次只能移动一个值”的限制。
- 适用性： 计数排序在此类问题中表现出色，但它依赖于待排序元素是整数且范围相对较小。如果元素是浮点数、字符串或整数范围非常大，则计数排序可能不再适用或效率低下。
总结
针对给定栈中特定范围整数的排序问题，计数排序提供了一个极其高效的解决方案。通过将问题分解为频率统计和按序重建两个清晰的步骤，我们能够以线性时间复杂度O(N)完成排序，同时仅使用常数级别的额外空间O(1)。这种方法不仅在性能上远超传统的比较排序算法，也巧妙地遵守了每次只能移动一个值的操作限制。理解并应用这类针对特定场景优化的算法，是提升程序性能的关键。
