Neil Ding
Neil Ding
用Heap求第K大元素的Java代码，这个方法确实没有quicksort的方法好，不过借此机会来复习一下Heap也不错。算法的原理不复杂，但实现起来却比较麻烦，主要需要考虑**“数组越界”**的情况和使用while循环来**“iteratively找到元素合适位置”**。 ``` java // define error message, not a good way, throw error is better public static int ERROR_NUM = Integer.MIN_VALUE; // turn array into heap static void heapify(int[] arr,...
@allen6432 tries? 没有听说过诶，好像很高级。那这光荣的任务就交给你啦！
太给力了， @allen6432 这推导果然高大上，看了几遍有几步还是没明白，那我就不耻下问了。  
cheer!
@allen6432 我又来不耻下问了 1. 能不能解释一下`T(n) = T(n/2) + O(n)`这个表达式是什么意思？以及它是这么得来的？ 2. 为啥每次看到`n/2`，就用`2^a = n`来代替？
来趁热打铁写一个merge sort，这里使用比较好理解的递归的方法，这个算法一般需要使用额外空间。额外空间使用的位置是merge两个数组的时候，需要一个更长的数组存放merge的结果。 在理想状况下正好能均分（强迫症患者的福音），试着考虑一下空间的使用情况，第一次merge应该发生在数组被切分到最细的时候，在最细的那一层，merge的是两个只有一个元素的数组，它使用了`2`个额外的空间返回合并的结果，在这一层共发生了`n/2`次merge，乘一下得出在最细层使用了`n`个额外空间。在往上一层，merge的是两个包含两个元素的数组，需要`4`个额外空间来存结果，在这一次发生了`n/4`次merge，乘一下还是`n`。以此类推直到最后一次大merge，需要merge是两个长度为`n/2`的数组，长度还是n。 所有总共的空间使用情况就是，n乘以**“层数”**。如果数组长度是n，那层数是多少呢？换句话说，长度为n的数组，要劈多少次才能得到一个长度为1的数组呢（没法再劈了）？既然每劈一次一半，n就除以2，那么如果要劈k次的才能得到长度为1的数组，`n / (2^k) = 1`。算一下就是k = log2n，所以层数就是lgn了。 所以空间复杂度就是n \* log(n)个单位，即O(n log n)。 `=========================== 华丽分割 ===========================` 以上纯属是我的YY，看似很有道理，但其实是错的。 回过头来想想，其实空间是可以重复利用的，不像时间过去了就过去了，所以只需要一个长度为n的额外数组，就可以给满足不管是哪一层的哪一次merge的需求，所以其实空间复杂度是O(n)。给自己的一个教训就是，不要死钻牛角尖，跳出来想想可能会发现更加简单直接的方法。 另外，Merge Sort也有一些变种，可以做到不需要额外空间，成为in-place merge sort，这个就对编程能力是不小考验了，是一个不错的练习。 #### 奇怪的想法 我产生了一个奇怪的想法想请教一下大家，程序的效率跟merge的的个数有没有关系？如果每次分成三块呢？分成四块呢？直接分成n块呢？ #### 常规代码 ```...
@allen6432 也就是说，虽然变化不大，但效率还是有少量提升？
@allen6432 我后来也看了一下，标准做法是把第一个空出，但不空也是可以的，就是麻烦一点。
@allen6432 赶紧的啊，再不回来这都要发芽了