题目

棘手点：

shell的sort命令，采用了归并排序，排序时候的临时小文件是默认放在/tmp路径下的，有时候/tmp的空间有限制，比如4G，那么，超过4G的文件就没有办法用sort了。当然也可以用sort -T Path 来临时文件的目录。

python的sort

java的sort

C++的sort

1.如果是无重复整型，果断位排序，（编程珠玑有介绍）。
2.如果有重复的整型，果断计数排序，
3.如果是字符串，果断字典树来排序啊。。当然，就算不是字典树，我们也可以转化为字典树来解答。。

遍历一次，累计给定的数大于多少个元素，不就是准确的排行么？
如果要大概，也可以抽样，累计大于样本的数目，估计一个百分比。
如果题目是指，遍历一次后，需求任意个数的排行，那么可在遍历时生成直方图，然后转为累计直方图，最后可以直方图区间插值得出估计的排行。

特点，它是读取次数最少得排序，因为若内存空间不足，则必须将数据存在硬盘中，要尽量减少I/0的次数。

1.快速排序的概率时间是接近o（n）的，是几种 nlogn中最好的
2.快速排序的空间复杂度是 o（n）的，优于归并的 o（2n）
3.内存的好处就是读取存取速度快，而恰恰快排是依赖R/W的排序

A: 当数据本身有一定次序时，快排会退化为o(n^2)
B: 恩，不过这种情况一般不会发生，可以通过random参数来fix的，算法导论排序那章讨论过这个特例和fix方法的。

请问一下为什么快排的空间复杂度是O(n)呢？。不是原地排序吗？是递归使用的栈内存吗？

O（n）
这算脑筋急转弯