PHP 数组排序算法复杂度:冒泡排序: O(n^2)快速排序: O(n log n) (平均)归并排序: O(n log n)
PHP 数组排序算法的复杂度分析
在 PHP 中,有多种排序算法可用于对数组中的元素进行排序。每种算法的效率各不相同,这取决于数组的大小和数据分布。
冒泡排序
冒泡排序是一种简单的排序算法,但效率较低。它通过反复比较相邻元素并交换较大的元素到数组末尾来工作。
function bubbleSort($arr) { for ($i = 0; $i < count($arr); $i++) { for ($j = 0; $j < count($arr) - $i - 1; $j++) { if ($arr[$j] > $arr[$j + 1]) { $temp = $arr[$j]; $arr[$j] = $arr[$j + 1]; $arr[$j + 1] = $temp; } } } return $arr; }
时间复杂度:O(n^2)
快速排序
快速排序是一种分治算法,通常被认为是效率最高的排序算法。它使用递归来将数组划分为较小的子数组,并对每个子数组进行排序。
function quickSort($arr) { if (count($arr) <= 1) { return $arr; } $pivot = $arr[count($arr) - 1]; $left = []; $right = []; for ($i = 0; $i < count($arr) - 1; $i++) { if ($arr[$i] < $pivot) { $left[] = $arr[$i]; } else { $right[] = $arr[$i]; } } return array_merge(quickSort($left), [$pivot], quickSort($right)); }
时间复杂度:O(n log n) (平均情况下)
归并排序
归并排序也是一种分治算法。它通过递归将数组划分为较小的子数组,对子数组进行排序,然后合并排序的子数组来工作。
function mergeSort($arr) { if (count($arr) <= 1) { return $arr; } $mid = count($arr) / 2; $left = mergeSort(array_slice($arr, 0, $mid)); $right = mergeSort(array_slice($arr, $mid)); return merge($left, $right); } function merge($left, $right) { $merged = []; $i = $j = 0; while ($i < count($left) && $j < count($right)) { if ($left[$i] <= $right[$j]) { $merged[] = $left[$i]; $i++; } else { $merged[] = $right[$j]; $j++; } } return array_merge($merged, array_slice($left, $i), array_slice($right, $j)); }
时间复杂度:O(n log n)
实战案例
假设您有一个包含 10000 个整数的数组。您可以使用上述算法对该数组进行排序,并使用 PHP 的 microtime() 函数测量排序所需的时间。
$arr = range(1, 10000); shuffle($arr); // 打乱数组以获得更现实的结果 $timeStart = microtime(true); bubbleSort($arr); $timeEnd = microtime(true); echo "Bubble Sort: " . ($timeEnd - $timeStart) . " 秒\n"; $timeStart = microtime(true); quickSort($arr); $timeEnd = microtime(true); echo "Quick Sort: " . ($timeEnd - $timeStart) . " 秒\n"; $timeStart = microtime(true); mergeSort($arr); $timeEnd = microtime(true); echo "Merge Sort: " . ($timeEnd - $timeStart) . " 秒\n";
对于包含 10000 个整数的数组,结果如下:
Bubble Sort: 1.0129920272827 秒 Quick Sort: 0.001443982124329 秒 Merge Sort: 0.001151084899902 秒
结果表明,快速排序和归并排序明显比冒泡排序更有效。
以上是各种 PHP 数组排序算法的复杂度分析的详细内容。更多信息请关注PHP中文网其他相关文章!