请教如何对文本文件内容进行排序，请提供一个比较有效率的设计思路

Question

还有就是通过算法,把文件分成几块,每块分别排序,然后再是块与块之间的排序
具体的代码去找本<<数据结构>>,当中的排序算法中好像有一个快速算法可以这样用的。

Answer 1

用内存是最好的办法
Unix下的sort似乎是写到/tmp下的缓存里面

Answer 2

Sort命令也是很耗内存的...如果你想最大限度的节约内存.那么StreamReader,每次只用读两行.进行冒泡排序...

Answer 3

我有个思路如下,首先先确定文件的大致大小和可以使用内存而不占用虚拟页面文件的内容大小假设文件是500M,  可以在此使用的内存是150兆, 那么把文件分割为5份,每次读取一份以后在内存中排序 (因为在内存中进行,其实排序时交换内容使用的内存量可以忽略---只有1行数据)然后写入一个临时文件.最后得到5个临时文件用5个读取器分别按行读5个文件,每读1行就比较5个的大小(当然,才5个,也是在内存里比了),然后最大的写入目标文件,再从最大的那个的源临时文件读下一行.以此循环到读完为止.
这样总的读取硬盘记录数为2n(假设原文件共n行),写硬盘记录数也是2n,总IO记录数是4n 
因为可能比较100次的时间也没一次IO操作久,所以最大限度减少IO操作,多比较几次问题不大了.

Answer 4

其实不管分多少块只要超过1块,那么最后的IO记录总数都是4n, 所以在这里分成10和分成5分成100都一样,但是分得越细需要的内存最少但需要的额外操作也越多(比如创建文件的IO操作)这里需要取一个合理的值,上面说的5个有点偏小了,其实可以更多.理论上,理想状态下(只有IO操作费时间,其他操作都是假设瞬间完成), 应该是总记录数开平方.就是假设文件里有一亿行记录,分开成1万个文件是最省内存的,而且总的读写操作也一样是4n (不过多了10000次创建文件的操作..)为什么是开平方呢,因为这样可以使前面分组时的内存比较和后面循环读取时的比较的规模一样大,最大限度节约了内存,如果分再细,在后面循环读取时会费更多内存,分再少,则前面费更多内存.但是具体情况毕竟不是理想状态,还要根据比较算法的耗时和其他具体上下文环境来判断.但有一点是肯定的就是主要矛盾是在IO操作上,在其他地方去追求极致也不如IO省点,其他地方多花点,毕竟写内存比写硬盘快1000倍.

Answer 5

shrinerain(圣影雨) 说的读2行进行冒泡排序,内存是省了,但是IO次数绝对不可接受,总需要的IO记录数是读取记录次数: (n*n+n)/2
写记录次数: n*n - n 总合远大于 4n (n很大)

Answer 6

to syeerzy(快乐永远*先天下之乐而乐*后天下之忧而忧*)每次150兆肯定会用虚存的，不管你内存有多大
不信你试一下//那么StreamReader,每次只用读两行.进行冒泡排序
我倒认为这个方案可行，相邻行的读写，其实是缓冲区的内容
操作系统不会傻到读一行就把内部缓冲区清掉
写的过程恐怕要用临时文件

Answer 7

你用一个150兆的文本文件，一次性读到一个字符串，然后以\r\n分隔Split到字符串数组
与ReadLine到数组
两种方式比较一下，哪个快，就知道了~

Answer 8

syeerzy说的有点道理
我总结了一下思路：
1.如果文件大小低于某个值（比如小于物理可用内存)，可以全部读入物理内存进行排序
我的想法是定制一个结构，并实现IComparable接口，用Array.sort()方法进行排序。
2.如果文件大于某个值，全部读入内存会造成频繁使用虚拟内存。则将文件分割成几快，读入内存进行排序后形成几个临时文件。同时读取这几个临时文件，对几个文件中的内容进行排序，写入最后的结果文件。确实这样做“读取硬盘记录数为2n(假设原文件共n行),写硬盘记录数也是2n”，硬盘IO是最耗资源。
3.最后实现还是要考虑不少问题，比如内存使用大小和产生临时文件多少的平衡点。
欢迎大家继续讨论，找出更好的处理方法

Answer 9

//那么StreamReader,每次只用读两行.进行冒泡排序能再具体点说明一下实现方式吗？