使用PHP测试冒泡和快速排序两种算法的执行时间，以及分析循环次数

先上结果

• 数组元素个数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