php怎么从一个无序数组中找中数-PHP问题-PHP中文网

php怎么从一个无序数组中找中数

PHPz

发布： 2023-04-23 16:46:23

原创

997人浏览过

在php中，数组是一种非常强大的数据结构。通过php数组，我们可以轻松地存储和操作大量的数据。但是，当我们需要从一个无序数组中找到中数时，该怎么做呢？

中数（也称为中位数）是一个数组中的中间值，它将数组分为两个部分，左边的所有值都比它小，右边的所有值都比它大。如果数组有偶数个元素，则中数是中间两个元素的平均值。

虽然php提供了sort（）函数，可以用来对数组进行排序，但是该函数在对大数组进行排序时，时间复杂度会达到O（nlogn），并且会修改数组的排序顺序，这不是我们所想要的。

那么，我们如何在PHP中查找一个无序数组的中数，同时又不改变数组的顺序呢？下面就让我们一起来看看。

利用快速排序查找中数

快速排序算法是一种基于比较的排序算法，它在平均情况下的时间复杂度为O（nlogn），并且不需要额外的内存空间。因此，我们可以使用快速排序来对数组进行排序，并查找中数。

立即学习“PHP免费学习笔记（深入）”；

快速排序算法的主要思路是选择数组中的一个基准元素，然后将数组分为两个部分，一个部分包含所有小于基准元素的值，另一个部分包含所有大于基准元素的值。然后递归地对这两个部分进行排序，直到整个数组都有序。

为了找到无序数组的中数，我们可以通过快速排序算法来先将其排序，然后再根据排序后数组的长度来确定中数。

以下是利用快速排序查找中数的PHP代码示例：

function quickSort($arr){
    $len = count($arr);
    if($len <= 1){
        return $arr;
    }
    $pivot = $arr[0];
    $left_arr = array();
    $right_arr = array();
    for($i=1; $i<$len; $i++){
        if($arr[$i] <= $pivot){
            $left_arr[] = $arr[$i];
        }else{
            $right_arr[] = $arr[$i];
        }
    }
    $left_arr = quickSort($left_arr);
    $right_arr = quickSort($right_arr);
    return array_merge($left_arr, array($pivot), $right_arr);
}

$arr = array(3, 9, 2, 7, 1, 5, 6);
$sorted_arr = quickSort($arr);
$len = count($sorted_arr);
if($len % 2 == 0){
    $middle = ($sorted_arr[$len/2-1] + $sorted_arr[$len/2])/2;
}else{
    $middle = $sorted_arr[($len-1)/2];
}
echo "中数为：".$middle;

登录后复制

利用堆排序查找中数

堆排序算法是一种基于堆的树形数据结构的排序算法。在堆排序中，我们通过构建一个最大堆或者最小堆来对数组进行排序。我们可以使用最大堆来查找无序数组的中数。

PHP经典实例(第二版)

PHP经典实例（第2版）能够为您节省宝贵的Web开发时间。有了这些针对真实问题的解决方案放在手边，大多数编程难题都会迎刃而解。《PHP经典实例(第2版)》将PHP的特性与经典实例丛书的独特形式组合到一起，足以帮您成功地构建跨浏览器的Web应用程序。在这个修订版中，您可以更加方便地找到各种编程问题的解决方案，《PHP经典实例(第2版)》中内容涵盖了：表单处理；Session管理；数据库交互；使用We

453

查看详情

最大堆是一种满足以下性质的二叉树：

1、堆的每个节点的值都大于或等于其左右子节点的值。

2、堆总是一棵完全二叉树。

对于一个无序数组，我们可以通过构建一个最大堆来将其排序。然后，我们就可以根据最大堆的性质找到中数了。

以下是利用堆排序查找中数的PHP代码示例：

function buildMaxHeap(&$arr, $index, $heapSize){
    $left = 2*$index+1;
    $right = 2*$index+2;
    $max = $index;
    if($left<$heapSize && $arr[$left]>$arr[$max]){
        $max = $left;
    }
    if($right<$heapSize && $arr[$right]>$arr[$max]){
        $max = $right;
    }
    if($max != $index){
        $temp = $arr[$index];
        $arr[$index] = $arr[$max];
        $arr[$max] = $temp;
        buildMaxHeap($arr, $max, $heapSize);
    }
}

function heapSort(&$arr){
    $heapSize = count($arr);
    for($i=intval($heapSize/2)-1; $i>=0; $i--){
        buildMaxHeap($arr, $i, $heapSize);
    }
    for($i=$heapSize-1; $i>=1; $i--){
        $temp = $arr[0];
        $arr[0] = $arr[$i];
        $arr[$i] = $temp;
        $heapSize--;
        buildMaxHeap($arr, 0, $heapSize);
    }
}

$arr = array(3, 9, 2, 7, 1, 5, 6);
heapSort($arr);
$len = count($arr);
if($len % 2 == 0){
    $middle = ($arr[$len/2-1] + $arr[$len/2])/2;
}else{
    $middle = $arr[($len-1)/2];
}
echo "中数为：".$middle;

登录后复制

总结

以上是两种在PHP中查找无序数组中数的方法。虽然它们的时间复杂度不一样，但它们都可以实现对无序数组的快速排序和查找中数的功能。如果您需要对大量的无序数组进行排序和查找中数，那么建议您使用堆排序算法来实现，它有着更好的时间复杂度表现。

以上就是php怎么从一个无序数组中找中数的详细内容，更多请关注php中文网其它相关文章！