我正在实现一个程序来对可能不适合内存的大文件进行排序。所有文件都将按行排序，因此我正在考虑使用 List 来执行此操作。
我已经计算了内存中有多少行可以将文件拆分为较小的文件，但我不知道内存中需要多少空间来对 N 个元素的列表进行排序。
问题是，知道元素的最大数量（已知大小的字符串）和可用内存，List.Sort 方法需要多少内存空间？
问问题
916 次
3 回答
3
List<T>.Sort使用快速排序算法，即 O(log n) 空间。
于 2012-07-13T15:37:06.827 回答
2
快速排序是O(logn)空间复杂性，因为它在每个递归级别存储常量信息（分区的开始和结束），并且在大多数logn级别都有。
合并本身是就地的，冒泡排序后备也是如此，因此它们O(1)不计在内。
于 2012-07-13T15:39:39.197 回答
2
做一些研究：List.Sort()默认使用QuickSort算法，它具有 O(logn) 空间复杂度。
如果您真的担心空间复杂度并且不介意较慢的算法，您可以使用具有 O(1) 空间复杂度的冒泡排序。
于 2012-07-13T15:39:57.983 回答