您的位置：首页 > 技术中心 > PHP教程 >

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

时间：2023-04-23 19:26

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

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

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

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

利用快速排序查找中数

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

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

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

以下是利用快速排序查找中数的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;

利用堆排序查找中数

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

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

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怎么从一个无序数组中找中数的详细内容，更多请关注Gxl网其它相关文章！