12 | 排序（下）：如何用快排思想在O(n)内查找第K大元素？

每次从各个文件中取一条数据，在内存中根据数据时间戳构建一个最小堆，然后每次把最小值给写入新文件，同时将最小值来自的那个文件再出来一个数据，加入到最小堆中。这个空间复杂度为常数，但没能很好利用1g内存，而且磁盘单个读取比较慢，所以考虑每次读取一批数据，没了再从磁盘中取，时间复杂度还是一样O(n)。

伪代码反而看得费劲，可能还是对代码不够敏感吧

先构建十条io流，分别指向十个文件，每条io流读取对应文件的第一条数据，然后比较时间戳，选择出时间戳最小的那条数据，将其写入一个新的文件，然后指向该时间戳的io流读取下一行数据，然后继续刚才的操作，比较选出最小的时间戳数据，写入新文件，io流读取下一行数据，以此类推，完成文件的合并， 这种处理方式，日志文件有n个数据就要比较n次，每次比较选出一条数据来写入，时间复杂度是O（n），空间复杂度是O（1）,几乎不占用内存，这是我想出的认为最好的操作了，希望老师指出最佳的做法！！！

还是觉得伪代码更好，理解思路然后可以写成自己写练练手，看完代码后就没啥想写的欲望了。

我是一个笨的人，一节课要看很多遍，但是我知道，只要比聪明的人多看几遍，就也会达到同样的效果

当 T(n/2^k)=T(1) 时，也就是 n/2^k=1 这个为什么会等于T(1)啊

大家都说快排的伪代码不好理解，我用JAVA翻译了一下，实测通过，老师给个置顶哈。private static void quickSortC(int[] a, int p, int r) { if (p >= r) { return; } int q = partition(a, p, r); quickSortC(a, p, q - 1); quickSortC(a, q + 1, r); } public static int partition(int[] a, int start, int end) { int pivot = a[end]; int i = start; for (int j = start; j < end; j++) { if (a[j] < pivot) { swap(a, i, j); i = i + 1; } } swap(a, i, end); return i; }

老师 这个地方我没看懂... “第一次分区查找，我们需要对大小为 n 的数组执行分区操作，需要遍历 n 个元素。第二次分区查找，我们只需要对大小为 n/2 的数组执行分区操作，需要遍历 n/2 个元素。依次类推，分区遍历元素的个数分别为、n/2、n/4、n/8、n/16.……直到区间缩小为 1。” 这里讨论的是最平均的情况吗？ 最坏的情况可以n,n-1,...,1啊

你可能会说，我有个很笨的办法，每次取数组中的最小值，将其移动到数组的最前面，然后在剩下的数组中继续找最小值，以此类推，执行 K 次，找到的数据不就是第 K 大元素了吗？ 应该是每次取数组中的最“大”值放到前面吧，因为找的是第k大元素？

快排的partition函数的空间复杂度是O(1)，但整个排序过程是递归的，最多会有O(logn)个函数放在栈里。这一部分不算空间复杂度么？