找数组中给定下标区间内的第K小(大)元素

今晚看了下MIT的算法导论公开课,发现一道题很有意思,涉及到多种算法的实现,就记下来以后再回顾。 给定数组,给定区间,求第K小(大)小的数如何处理?。     1、排序,快速排序。我们知道,快速排序平均所费时间为n*logn,从小到大排序这n个数,然后再遍历序列中后k个元素输出,即可,总的时间复杂度为O(n*logn+k)=O(n*logn)。     2、排序,选择排序。用选择或交换排序,即遍历n个数,先把最先遍历到得k个数存入大小为k的数组之中,对这k个数,利用选择或交换排序,找到k个数中的最小数kmax(kmax设为k个元素的数组中最小元素),用时O(k)(你应该知道,插入或选择排序查找操作需要O(k)的时间),后再继续遍历后n-k个数,x与kmax比较:如果x<kmax,则x代替kmax,并再次重新找出k个元素的数组中最大元素kmax‘(多谢jiyeyuran 提醒修正);如果x<kmax,则不更新数组。这样…

Continue Reading