对堆栈进行排序的更好方法/算法改进+空间和时间推理

Question

我正试图找出以下问题的最佳解决方案：

给定一个20整数堆栈，对堆栈进行排序，使从CCD_ 2到CCD_。您只能移动一个值一次。

我已经实现了一个迭代&递归快速排序&现在我正在寻找更优化的解决方案。到目前为止，我已经提出了以下内容，它在10k次迭代中平均运行速度快约10倍。我正在努力思考关于太空的理由；时间复杂性&我相信有足够的空间可以找到更好的解决方案。

我应该考虑哪种？我应该考虑哪些数据类型？给定问题的最佳可能最坏情况时间复杂度O(？(是多少？

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);

HashMap<Integer, Integer> map = new HashMap<>();
map.put(1, 0);
map.put(2, 0);
map.put(3, 0);
map.put(4, 0);

int popped;

while (!stack.isEmpty()) {
popped = stack.pop();

if (map.containsKey(popped)) {
map.put(popped, map.get(popped) + 1);
}
}

while (map.get(4) > 0) {
stack.push(4);
map.put(4, map.get(4) - 1);
}

while (map.get(3) > 0) {
stack.push(3);
map.put(3, map.get(3) - 1);
}

while (map.get(2) > 0) {
stack.push(2);
map.put(2, map.get(2) - 1);
}

while (map.get(1) > 0) {
stack.push(1);
map.put(1, map.get(1) - 1);
}

Answer 1

您正在重新发明Counting排序算法，该算法在线性时间内运行O(n(。

您可以使用普通数组来代替HashMap。而且您肯定不需要这群冗余的while循环。

以下是伪代码中的算法描述：

function CountingSort(input, k)

count ← array of k + 1 zeros
output ← array of same length as input
for i = 0 to length(input) - 1 do      // STEP 1
j = key(input[i])
count[j] = count[j] + 1
for i = 1 to k do                      // we don't need this step
count[i] = count[i] + count[i - 1]
for i = length(input) - 1 down to 0 do // STEP 2
j = key(input[i])
count[j] = count[j] - 1
output[count[j]] = input[i]
return output

对于您的用例，您不需要计算累积频率的第二个for-循环。

因此，为了解决这个问题，我们需要采取以下步骤：

• 步骤1是生成频率直方图。

• 步骤2是向后迭代频率(即从数组的最后一个索引开始(，并推送等于index+minValue的值(在这种情况下为1(。每个值应该被推送与其频率相等的次数。

这里有一个实现：

final int min = 1;
final int max = 4;
int[] freq = new int[max - min + 1]; // histogram, i.e. array of frequencies of values in range [min, max]

// STEP 1: generating a histogram
while (!stack.isEmpty()) {
int next = stack.pop();
if (next >= min && next <= max) freq[next - min]++; // calculating the frequency of each element
}

// STEP 2: populating the stack in sorted order

for (int i = freq.length - 1; i >= 0; i--) {
while (freq[i] > 0) {
stack.push(i + min);
freq[i]--;
}
}
return stack;

如果您想使用HashMap，那么，您可以应用相同的算法，只是不要创建冗余循环。

关于这两种情况下的时间复杂性，正如我之前所说，它将是线性。数组的性能会稍好一些，但更重要的是，它能让您更好地了解算法的内部机制。

final int min = 1;
final int max = 4;

Map<Integer, Integer> freq = new HashMap<>(); // histogram, i.e. array of frequencies of values in range [min, max]
// STEP 1: generating a histogram

while (!stack.isEmpty()) {
int next = stack.pop();
if (next >= min && next <= max) 
freq.merge(next, 1, Integer::sum); // calculating the frequency of each element
}

// STEP 2: populating the stack in sorted order

for (int i = max; i >= min; i--) {
int count = freq.get(i);
while (count > 0) {
stack.push(i + min);
count--;
}
}

return stack;

旁注：类java.util.Stack是遗留的，不鼓励使用。当您需要在Java中实现Stack数据结构时，请使用实现Deque接口的类。