在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;- 利用堆排序查找中数
堆排序算法是一种基于堆的树形数据结构的排序算法。在堆排序中，我们通过构建一个最大堆或者最小堆来对数组进行排序。我们可以使用最大堆来查找无序数组的中数。
最大堆是一种满足以下性质的二叉树：
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中查找无序数组中数的方法。虽然它们的时间复杂度不一样，但它们都可以实现对无序数组的快速排序和查找中数的功能。如果您需要对大量的无序数组进行排序和查找中数，那么建议您使用堆排序算法来实现，它有着更好的时间复杂度表现。
