o(n^)级别的排序算法和php原生sort性能对比

今天药忘吃喽~ 2022-05-20 07:56 40阅读 0赞

测试样本为5000

测试结果

原生sort:0.002000093460083 冒泡排序:3.9222249984741 选择排序:2.8271610736847 插入排序:1.9501118659973 希尔排序:0.053003072738647

希尔排序为o(n^)级别排序算法中最快的算法

以下为测试代码

/* * 检查排序结果是否正确 * @param array array 测试数据样本 * @param n int 测试样本数量 * */ function checkArraySort($array,$n){
        for($i = 0;$i < $n - 1;$i++){
            if($array[$i] > $array[$i + 1]){
                return false;
            }
        }
        return true;
    }
    
    /* * 冒泡排序 * @param array array 测试数据样本 * @param n int 测试样本数量 * */ function mpSort($array,$n){
        for($i = 0;$i < $n;$i++){
            $flag = 0;
            for($j = $i + 1;$j < $n;$j++){
                if($array[$i] > $array[$j]){
                    $temp = $array[$i];
                    $array[$i] = $array[$j];
                    $array[$j]= $temp;
                }
            }
        }
        if(!checkArraySort($array,$n)){
            echo 'error';
            exit;
        }
    }
    
    /* * 拆入排序 * @param array array 测试数据样本 * @param n int 测试样本数量 * */ function insertSort($array,$n){
        for($i = 1;$i < $n;$i++){
            $e = $array[$i];
            for($j = $i;$j > 0 && $array[$j - 1] > $e;$j--){
               $array[$j] = $array[$j - 1];
            }
            $array[$j] = $e;
        }
        if(!checkArraySort($array,$n)){
            print_r($array);exit;
            echo 'error';
            exit;
        }
    }
    
    /* * 选择排序 * @param array array 测试数据样本 * @param n int 测试样本数量 * */ function selectSort($array,$n){
        for($i = 0;$i < $n;$i++){
            $minIndex = $i;
            for($j = $i + 1;$j < $n;$j++){
                if($array[$minIndex] > $array[$j]){
                    $minIndex = $j;
                }
           }
            if($minIndex != $i){
                $temp = $array[$minIndex];
                $array[$minIndex] = $array[$i];
                $array[$i] = $temp;
            }
        }
        if(!checkArraySort($array,$n)){
            echo 'error';
            exit;
        }
    }
    
    /* * 希尔排序 * @param array array 测试数据样本 * @param n int 测试样本数量 * */ function shellSort($array,$n){
        $f = 2;
        for ($gap = $n / $f; $gap > 0; $gap = intval($gap / $f)){
            for($i = $gap; $i < $n;$i++){
                $j = $i;
                while($j - $gap >= 0 && $array[$j] < $array[$j - $gap]){
                    $temp = $array[$j];
                    $array[$j] = $array[$j-$gap];
                    $array[$j-$gap] = $temp;
                    $j -= $gap;
                }
            }
        }
        if(!checkArraySort($array,$n)){
            echo 'error';
            exit;
        }
    }
    
    /* * 测试排序算法 * @param functionDesc string 排序函数描述 * @param functionName string 排序函数名称 * @param array array 测试数据样本 * */ function testArray($functionDesc,$functionName,$array){
        $n = count($array);
        $startTime = microtime(true);
        $functionName($array,$n);
        $endTime = microtime(true);
        $time = $endTime - $startTime;
        echo "{
       $functionDesc}:{
       $time}<br>";
    }
    
    /* * 生成测试数据 * @param arrayNumber int 生成测试数据的数量 * @param randMin int 生成测试数据的最小值 * @param randMax int 生成测试数据的最大值 * return array * */ function generateTestData($arrayNumber,$randMin = 0,$randMax = 0){
        if($randMax == 0){
            $randMax = $arrayNumber;
        }
        for($i = 0; $i < $arrayNumber; $i++){
            $array[] = mt_rand($randMin,$randMax);
        }
        return $array;
    }
    
    $array = generateTestData(5000);
    $array1 = $array;
    $array2 = $array;
    $array3 = $array;
    $array4 = $array;
    testArray("原生sort",'sort',$array);
    testArray("冒泡排序",'mpSort',$array1);
    testArray("选择排序",'selectSort',$array2);
    testArray("插入排序",'insertSort',$array3);
    testArray("希尔排序",'shellSort',$array4);