新浪博客

线性时间查找序列第k小数的算法

2011-03-27 16:16阅读：

http://blog.sina.cn/dpool/blog/u/1516307152

这学期学习算法分析与设计课程，今天看了看中位数，总结了总结算法，实现代码一会儿再贴
Description：
从一组输入数据中找出第k小的数，要求在线性时间内作出选择。
Solution：
传统的方法是对这组数据 进行排序（插入冒泡等），然后从排序后的序列中比较找出第k小的数，但是这种方法复杂度是O(nlogn)(采用快速排序)
为了在线性时间内得到结果，又如下方法,假设输入数组为a[]：
方法一： 类似于二分排序
Select(int[] a, int start, int end, int k)

{
//利用快速排序方法，将数组以pivot值分成两部分，下标为j
j = Partition(a,start,end);
//利用pivot值的下标j与k进行比较：
If( k = j)
Return a[j]
If( k < j )
//表示第k小的数在前半部分，则对前部分递归调用此方法
Select(a,start,j-1,k);
If( k > j )
//表示第k小的数在后半部分，则对后部分递归调用此方法
Select(a,j+1,end,k-j);
}
分析：此种方法的平均时间复杂度是O(n);但是在最坏情况下，可能总是按剩下的元素中最大的进行划分，则复杂度为O(n*n)，因此如果能在线性的时间内找到划分的基准，则可以在最坏情况下复杂度为O(n)时找到第k小的数。具体看下面的方法。
方法二： 在O(n)下找到划分基准。
1. 找基准
(a) 将数组a五个数为一组，分成[n/5]个组
(b) 对[n/5]个组的数进行组内排序，采用冒泡就行
(c) 选择b中每组的中位数，将这些中位数交换到数组的最前面，此时a[0-(end-start)/5 -1]中存的就是这些中位数
(d) 对c中的0-(end-start)/5 -1个中位数进行排序，取出排序后这些中位数的中位数x。
X就是需要的基准。
2. 以x为基准进行划分，剩下的方法同方法一，即划分，比较，递归寻找。
分析：此种方法的最坏情况下复杂度也是O(n)

我的更多文章

下载客户端阅读体验更佳

APP专享