写未排序连续串阵列有效地分类成文件 [英] write unsorted consecutive strings array sorted into a file efficiently

问题描述

我有一个包含无序的连续编号（范围从0到n）字符串数组，例如： [7A，1B，2C，0D，6E，5F，3G，4H] ，我想写的数字，以便到一个文件中。

I have an array of strings containing unordered consecutive numbers (range from 0 to n), e.g. [7a, 1b, 2c, 0d, 6e, 5f, 3g, 4h], and I want to write the numbers in order into a file.

例如后：

0d
1b
2c
3g
4h
5f
6e
7a

的字符串并不都是相同的长度。

The string are not all the same length.

我试图找到一种方法来做到这一点既快速又没有采取太多的空间。我找到了一种方法，我可以在O（n）的空间复杂度和O（n）性能做到这一点：我创建N个单元阵列，并插入每个字符串自己的手机号码

I was trying to find a way to do it both fast and without taking too much space. I found a way that I can do it in O(n) space complexity and O(n) performance: I create an array with n cells and insert each string to his cell number.

for (i = 0; i < n; i++)
   sortedArray[originalArray[i]] = originalArray[i]

...类似的东西（在原来的规模创造新的数组并填写在一个运行），然后用另一个循环写排序的数组的内容到文件中。

... something like that (creating new array in the size of the original one and fill it in one run), and then with another for loop write the content of the sorted array into the file.

但我在寻找一个更好的方式来做到这一点。

But I am looking for a better way to do it.

推荐答案

假设你的字符串领先的数字确实是连续的和不重复的，你就不会取得更好的时间复杂度比超过你会与你所描述的方法这个问题，或类似的规定。它需要的工作空间正比于字符串的数目。

Supposing that the leading numbers in your strings are indeed consecutive and non-repeating, you will not achieve better time complexity than than you would with the approach you describe in the question, or something along those lines. It requires work space proportional to the number of strings.

在比较，

• 在一个标准的归并排序也需要办公空间的比例为字符串的数量（但你可以逃脱的一半之多，在这个问题的方法，如果你很小心），并具有为O（n log n）的时间复杂度。另外，
• 在快速排序排序就地并具有为O（n log n）的时间平均复杂性;如果你实现它精心那么只需要 O（log n）的最坏情况下的工作空间 - 在递归版本每堆栈帧恒定的量，或叠层容在一个非递归一个许多元素。
• 就地合并排序，需要 O（log n）的的工作空间（而并不需要尽可能多的照顾，以实现这一一样快速排序），并具有平均为O（n ^ 2）时间复杂度。它往往打败其他大多数为O（n ^ 2）接近pretty的得心应手，大部分的时间。
• 插入排序排序就地并要求 O（1）的工作空间，但为O（n ^ 2）时间复杂度。它很好理解，易于实现，而且速度非常快在实践中较小的输入尺寸。

• a standard merge sort also requires work space proportional to the number of strings (but you can get away with half as much as the approach in the question, if you're careful), and it has O(n log n) time complexity. Alternatively,
• quick sort sorts in-place and has O(n log n) time complexity on average; if you implement it carefully then it requires only O(log n) work space in the worst case -- a constant amount per stack frame in the recursive version, or a stack accommodating that many elements in a non-recursive one.
• an in-place merge sort requires O(log n) work space (and doesn't require as much care to achieve that as does quick sort), and has O(n^2) time complexity on average. It tends to beat most other O(n^2) approaches pretty handily, most of the time.
• insertion sort sorts in-place and requires O(1) work space, but has O(n^2) time complexity. It's well understood, easy to implement, and very fast in practice for small input sizes.

有很多其他的替代品，但我认为这些是你的选择相当重presentative。哪一个最适合您需要依赖于您的问题大小的范围，以及你如何权衡的空间和速度。如果你的问题规模可能会非常大，而且你不能 O（N）空间开销，然后给快速排序慎重考虑。如果问题规模一定要小，但是空间的保护是非常重要的，然后再考虑插入排序。如果高速是重要的，你能承受的空间开销，那么你原来的做法是非常有吸引力的。

There are many other alternatives, but I think those are reasonably representative of your options. Which one best suits your needs depends on the bounds on your problem size, and on how you weigh space vs. speed. If your problem size can be very large, and you cannot afford O(n) space overhead, then give quick sort careful consideration. If the problem size is certain to be small, but space conservation is critically important, then consider insertion sort. If high speed is important and you can afford the space overhead, then your original approach is awfully attractive.

这篇关于写未排序连续串阵列有效地分类成文件的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！