我有一个包含无序连续数字（范围从 0 到 n）的字符串数组，例如 [7a, 1b, 2c, 0d, 6e, 5f, 3g, 4h]，我想按顺序将数字写入文件。
示例后：
0d
1b
2c
3g
4h
5f
6e
7a
字符串的长度不同。
我试图找到一种方法来快速完成它，而不会占用太多空间。我找到了一种可以在 O（n） 空间复杂度和 O（n） 性能下做到这一点的方法：我创建一个包含 n 个单元格的数组，并将每个字符串插入他的单元格编号。
for (i = 0; i < n; i++)
sortedArray[originalArray[i]] = originalArray[i]
。类似的东西（以原始数组的大小创建新数组并在一次运行中填充它），然后使用另一个 for 循环将排序数组的内容写入文件。
但我正在寻找一种更好的方法来做到这一点。
假设字符串中的前导数字确实是连续且不重复的，那么您不会比您在问题中描述的方法或类似方法获得更好的时间复杂度。 它需要与字符串数量成比例的工作空间。
相比之下，
- 标准合并排序还需要与字符串数量成比例的工作空间（但如果你小心的话，你可以得到问题中方法的一半），并且它的时间复杂度
O(n log n)。 或者 - 快速排序就地排序，平均具有
O(n log n)的时间复杂度;如果你仔细实现它，那么在最坏的情况下它只需要O(log n)工作空间 - 递归版本中每个堆栈帧的恒定量，或者在非递归版本中容纳这么多元素的堆栈。 - 就地合并排序需要
O(log n)工作空间（并且不需要像快速排序那样小心地实现这一点），并且平均具有O(n^2)时间复杂度。 大多数时候，它往往很容易击败大多数其他O(n^2)方法。 - 插入排序就地排序，需要
O(1)工作空间，但时间复杂度O(n^2)。 它很好理解，易于实现，并且在实践中对于小输入尺寸非常快。
还有许多其他选择，但我认为这些可以合理地代表您的选择。 哪一个最适合您的需求取决于您的问题大小，以及您如何权衡空间与速度。 如果您的问题大小可能非常大，并且您无法承受O(n)空间开销，请仔细考虑快速排序。 如果问题大小肯定很小，但节省空间至关重要，请考虑插入排序。 如果高速很重要，并且您可以承受开销的空间，那么您的原始方法非常有吸引力。