c - 将未排序的连续字符串数组有效地排序到文件中

Question

我有一个字符串数组，其中包含无序的连续数字(范围从 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 循环将排序数组的内容写入文件。

但我正在寻找更好的方法。

Answer 1

假设您的字符串中的前导数字确实是连续且不重复的，您将不会获得比您在问题中描述的方法或类似的方法更好的时间复杂度。它需要与字符串数量成比例的工作空间。

相比之下，

• 标准合并排序还需要与字符串数量成比例的工作空间(但如果你小心的话，你可以用问题方法的一半来解决问题)，并且它有 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) 空间开销，那么请仔细考虑快速排序。如果问题规模肯定很小，但空间守恒很重要，那么考虑插入排序。如果高速很重要并且您可以负担得起空间开销，那么您原来的方法就非常有吸引力。