先上结果
-
数组元素个数1000时：
image.png -
数组元素个数10000时：
image.png
两次测试结果总结：
1：当数组元素数量增加10倍时，快速排序算法的消耗时间大概增加了10倍，而冒泡排序增加了100倍；
2：验证了两种算法的时间复杂度：快速排序平均时间复杂度 O(NlogN),冒泡排序时间复杂度 O(N^2)；
3：当数组元素数量在10^4数量级以上，冒泡排序算法基本上已经不适合使用了。
实现以上测试的代码
# sort.php
<?php
function floatTime() {
list($usec, $sec) = explode(' ', microtime());
return (float) ($sec + $usec);
}
/**
* bubbleSort 冒泡排序
* 最大时间复杂度 O(N^2)
* @Param array $arr [待排序的数组]
* @Return array $arr [排序后的数组]
*/
// 统计执行交换的次数
$loopCountBubble = 0;
function bubbleSort(array $arr): array {
$arrCount = count($arr);
if ($arrCount < 2) {
return $arr;
}
for ($i = $arrCount - 1; $i > 0; $i--) {
$exchange = false;
for ($j = 0; $j < $i; $j++) {
if ($arr[$j] > $arr[$j+1]) {
!$exchange && ($exchange = true);
GLOBAL $loopCountBubble;
$loopCountBubble++;
$arr[$j+1] = $arr[$j+1] - $arr[$j];
$arr[$j] = $arr[$j] + $arr[$j+1];
$arr[$j+1] = $arr[$j] - $arr[$j+1];
}
continue;
}
if (!$exchange) {
return $arr;
}
}
return $arr;
}
/**
* quickSort 快速排序
* 平均时间复杂度 O(NlogN)
* @Param array $arr [待排序的数组]
* @Return array $arr [排序后的数组]
*/
// 统计执行交换的次数
$loopCountQuick = 0;
function quickSort(array $arr):array {
$arrCount = count($arr);
if ($arrCount < 2) {
return $arr;
}
$mark = current($arr);
$leftArr = array();
$rightArr = array();
for($i = 1; $i < $arrCount; $i++) {
if ($arr[$i] >= $mark) {
$rightArr[] = $arr[$i];
} else {
$leftArr[] = $arr[$i];
}
GLOBAL $loopCountQuick;
$loopCountQuick++;
}
$leftArr[] = $mark;
$leftArr = quickSort($leftArr);
$rightArr = quickSort($rightArr);
return array_merge($leftArr, $rightArr);
}
// 初始化一个数组，用于测试
$range = range(1, 10000);
$arr = $range;
shuffle($arr);
echo 'origin array count: ' . count($arr) . "\n\n";
$startTimeQuick = floatTime();
$arrSortedByQuick = quickSort($arr);
$endTimeQuick = floatTime();
echo '===================Quick==================' . "\n";
echo 'quick loop count: ' . $loopCountQuick . "\n";
echo 'quick exec time: ' . ($endTimeQuick - $startTimeQuick) * 1000 . 'ms' . "\n\n";
$startTimeBubble = floatTime();
$arrSortedByBubble = bubbleSort($arr);
$endTimeBubble = floatTime();
echo '====================Bubble==================' . "\n";
echo 'bubble loop count: ' . $loopCountBubble . "\n";
echo 'bubble exec time: ' . ($endTimeBubble - $startTimeBubble) * 1000 . 'ms' . "\n";
## 到此结束
# 在终端执行
php sort.php
