叹为观止的算法基础经典

开篇第一章引论的第一节提出一个问题：

“设有一组N个数而要确定其中第K个最大者”

并给出两种解法

        全排序后返回K位置上的元素。平均复杂度O(NLogN)

        再建立一个临时数组，从N中读取K个数，全排序，然后依次读入其余N - K个数进来和第K名比较，大于K的值则插入到合适位置，只待循环完毕返回K位置元素。平均复杂度O(KLogK + (N - K))

这两种方法在N=100万，K=50万时速度都尤其“漫长“，往往让人抓耳挠腮，作者讲叙到还有一种算法1秒钟就可以得出答案。该算法原理和快速排序一致，但只有一个方向的递归。平均复杂度O(N)。

先选取一个中值元素（该中值是否合理将影响到算法效率），然后将大于等于该数的元素放到其左侧，小于该数的放到右侧，如7 4 6 8 0 -1 选取6作为中值元素，则结果应该为4 0 -1 6 8 7，接下来比较K值和现在的中值元素6所在索引(3)，如何小于3，则只需在索引0~2间再进行递归操作继续选取第K名，大于3则在4~5中递归选取第K - 3名即可。还有一关键是该为递归中的数组长度选取一临界点，小于该临界则进行选择排序，插入排序即可，比如20以内。

算法真是精妙，赶紧学习。