js获取一个未经排序数组的中位数
时间: 2024-05-31 13:07:05 浏览: 13
可以采用快速选择算法(QuickSelect),其基本思想与快速排序类似,但不需要对整个数组进行排序,只需要找到中位数所在的位置即可。
具体步骤如下:
1. 随机选择数组中的一个元素pivot,将数组分成两部分,左边的元素都小于等于pivot,右边的元素都大于等于pivot。
2. 计算pivot在排序后的位置,如果该位置等于中位数所在的位置,则直接返回pivot;否则判断该位置与中位数所在的位置的大小关系,如果该位置小于中位数所在的位置,则在右半部分继续查找;否则在左半部分继续查找。
3. 重复上述步骤,直到找到中位数所在的位置。
代码如下:
function findMedian(arr) {
var len = arr.length;
var mid = Math.floor(len / 2);
var left = 0, right = len - 1;
while (left <= right) {
var pivotIndex = partition(arr, left, right);
if (pivotIndex == mid) {
// 中位数为奇数个,直接返回pivot
if (len % 2 == 1) {
return arr[mid];
}
// 中位数为偶数个,计算中间两个数的平均值
else {
return (arr[mid] + arr[mid-1]) / 2;
}
}
else if (pivotIndex < mid) {
left = pivotIndex + 1;
}
else {
right = pivotIndex - 1;
}
}
}
function partition(arr, left, right) {
var pivotIndex = Math.floor(Math.random() * (right - left + 1)) + left;
var pivot = arr[pivotIndex];
swap(arr, pivotIndex, right);
var storeIndex = left;
for (var i = left; i < right; i++) {
if (arr[i] <= pivot) {
swap(arr, i, storeIndex);
storeIndex++;
}
}
swap(arr, storeIndex, right);
return storeIndex;
}
function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
示例:
var arr = [3, 1, 4, 2, 5];
console.log(findMedian(arr)); // 3
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)