php怎麼從一個無序數組找中數

在PHP中，陣列是一種非常強大的資料結構。透過PHP數組，我們可以輕鬆地儲存和操作大量的資料。但是，當我們需要從一個無序數組中找到中數時，該怎麼做呢？

中數（也稱為中位數）是一個陣列中的中間值，它將陣列分成兩個部分，左邊的所有值都比它小，右邊的所有值都比它大。如果數組有偶數個元素，則中數是中間兩個元素的平均值。

雖然php提供了sort（）函數，可以用來對數組進行排序，但是該函數在對大數組進行排序時，時間複雜度會達到O（nlogn），並且會修改數組的排序順序，這不是我們想要的。

那麼，我們要如何在PHP中找出一個無序數組的中數，同時又不改變數組的順序呢？下面就讓我們一起來看看。

1. 利用快速排序查找中數

快速排序演算法是一種基於比較的排序演算法，它在平均情況下的時間複雜度為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;

2. #利用堆排序來尋找中數

##堆排序演算法是一種基於堆的樹狀資料結構的排序演算法。在堆排序中，我們透過建立一個最大堆或最小堆來對數組進行排序。我們可以使用最大堆來找出無序數組的中數。

最大堆是一種滿足以下性質的二元樹：

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中文網其他相關文章！