将未排序的连续字符串数组有效地排序到文件中
我有一个包含无序连续数字的字符串数组（范围从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)空间开销，那么请仔细考虑。 如果问题规模确定很小，但空间保护至关重要，那么考虑插入排序。 如果高速是重要的，你可以承担太空间的开销，那么你原来的方法非常有吸引力。