叹为观止的算法基础经典
2006-12-26
开篇第一章引论的第一节提出一个问题:
“设有一组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以内。
算法真是精妙,赶紧学习。