笔试题经典算法：查找中位数

时间：2010-10-07 来源：kanong

查找中位数是面试中经常出现的一类题。用快速排序的思想可以解决这种问题，算法如下：

1.抽取数组的第一个元素作为中间值，用快速排序的思想进行一次调整，将比中间值小的放在中间值的左边，比中间值大的放在中间值的右边。

2.如果中间值的索引等于数组长度的一半，那么就找到了。

3.如果中位数的索引比数组长度的一半大的话，那么在中间值的索引到数组的结尾这个期间内找第（数组长度的一半-中位数）大的数。

4.否则在数组的开始到中间值的索引这段期间内找第（数组长度的一半大）大的数。

递归的调用上面的几步，就可以解决问题了！

上面可能说的太抽象啊了，具体的实现可以参考快速排序的实现，两者之间大同小异）。

代码如下：

/*
 *开 发 者：卡农
 *开发时间：2010-10-6
 *描    述：查找中位数 ， 算法的实现其实的快速排序的变种
 */
#include<iostream>
using namespace std;

/*
 *查找array数组里面array[left-right]第Max大的
 *参数：array      存储数据的数组
 *              left    数组的左界
 *      right   数组的右界
 *      Max             查找的第Max大
 */
void _f(int array[] , int left , int right , int Max){
        if(left>right){
                cout<<array[left+Max]<<endl;
                return;
        }

        int middle=array[left];
        int _left=left;
        int _right=right;
        while(_left<_right){
                while((_left<_right)&&(array[_right]>=middle)){
                        _right--;
                }
                array[_left]=array[_right];

                while((_left<_right)&&(array[_left]<=middle)){
                        _left++;
                }
                array[_right]=array[_left];
        }

        if((_left-left)==Max){
                cout<<array[_left]<<endl;
                exit(0);
        }

        if((_left-left)<Max){
                _f(array , _left+1 , right , Max-(_left-left)-1);
        }else{
                _f(array , left , _left-1 , Max);
        }
}


/*
 *查找中位数
 *参数：   array   存储数据的数组
 *                      length  数组的长度
 */
void f(int array[] , int length){
        _f(array , 0 , length-1 , length/2);
}


/*
 *测试用例
 */
void main(){
        int data[]={1,2,3,4,2,1,1,2,5,3,11};
    f(data , 11);
}

相关阅读更多 +