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