hanyeah

任意给一个数组，查找中位数。

引申一下，查找第N大的数。

找了一个基于快速排序的算法。

先写了一下快速排序。

快速排序代码如下：

<script>

var n = 10;
var arr=getRandomArr(n);
console.log(arr);
console.time("time");
quickSort(arr,0,n-1);
console.timeEnd("time");
console.log(arr);

/**
 * 快速排序
 * @param  {[type]} arr   [description]
 * @param  {[type]} start [description]
 * @param  {[type]} end   [description]
 * @return {[type]}       [description]
 */
function quickSort(arr,start,end){
	if(start>=end){
		return;
	}
	var i=start,j=end;
	var key = arr[i];
	while(i<j){
		if(arr[j]<key){
			arr[i] = arr[j];
			arr[j] = key;
			while(i<j){
				i++;
				if(arr[i]>key){
					arr[j]=arr[i];
					arr[i]=key;
					break;
				}
			}
		}
		j--;
	}
	quickSort(arr,start,i-1);
	quickSort(arr,i+1,end);
}

/**
 * 获取一个指定长度的随机数组。
 * @param  {[type]} n [description]
 * @return {[type]}   [description]
 */
function getRandomArr(n){
	var arr=[];
	for(var i=0;i<n;i++){
		arr.push(i);
	}
	arr.sort(function(a,b){
		return Math.random()>0.5?1:-1;
	});
	return arr;
}
</script>

查找第N大的数：

参考：http://blog.csdn.net/wangqinghao/article/details/8054366

参考文章中有点问题，自己改了一下。

代码如下：

<script>
//http://blog.csdn.net/wangqinghao/article/details/8054366
//https://www.cnblogs.com/hapjin/p/5769087.html

var n = 100;
var arr = getRandomArr(n);
console.log(arr);
var zhongweishu =  _f(arr, 0, n-1, Math.floor(n/2));
console.log(zhongweishu);

var m = Math.floor(Math.random()*n);
var mth =  _f(arr, 0, n-1, m);
console.log("从小到大第%d个数：%d",m,mth);

/*   
 *查找array数组里面array[left-right]第Max大的   
 *参数：array  存储数据的数组   
 *      left    数组的左界   
 *      right   数组的右界   
 *      Max     查找的第Max大   
 */  
function _f(array, left, right, Max){   
    if(left>right){  
        return array[left+Max];   
    }   
    
    var middle=array[left];   
    var _left=left;   
    var _right=right;   
    while(_left<_right){   
        while((_left<_right)&&(array[_right]>=middle)){   
            _right--;   
        }   
        array[_left]=array[_right]; 
        array[_right]=middle;  
    
        while((_left<_right)&&(array[_left]<=middle)){   
            _left++;   
        }   
        array[_right]=array[_left];
        array[_left]=middle;   
    }   
    
    if((_left-left)==Max){  
        return array[_left];
    }
    if((_left-left)<Max){   
        return _f(array , _left+1 , right , Max-(_left-left)-1);   
    }else{   
        return _f(array , left , _left-1 , Max);   
    }   
}   


/**
 * 获取一个指定长度的随机数组。
 * @param  {[type]} n [description]
 * @return {[type]}   [description]
 */
function getRandomArr(n){
	var arr=[];
	for(var i=0;i<n;i++){
		arr.push(i);
	}
	arr.sort(function(a,b){
		return Math.random()>0.5?1:-1;
	});
	return arr;
}
</script>