« 上一篇 下一篇 »

php的几个经典排序算法及时间复杂度和耗时​

    php排序算法是php的基础,而算法又是区分一个程序员水平高低的重要指标,这里总结了php比较经典的几个排序算法及测试各自的耗时,及其时间复杂度。

我首先想到的排序算法是这样的,那数组中的第一个数去跟其他元素比较,遇到比他小的元素即交换,然后继续比较,一个轮询下来确定第一位就是最小的,然后比较第二个元素,(我给他取名叫一般排序法),代码如下

function normal($arr,$length){
		$num = 0;
		for ($i=0; $i < $length; $i++) { 
			for ($j=$i+1; $j < $length; $j++) { 
				if ($arr[$i]>$arr[$j]) {
					$temp = $arr[$i];
					$arr[$i] = $arr[$j];
					$arr[$j] = $temp;
					$num++;	
				}
			}
		}
		echo "循环次数".$num."<br/>";
		echo "一般排序最终结果:".implode($arr,',')."<br/>";
	}

这个算法耗时怎么样呢,这里利用随机数生成一个10000长度的一个数组测试一下

$arr = [];
for ($i=0; $i < 10000; $i++) { 
	array_push($arr,rand(0,10000));
}

测试结果:排序用时(秒):5.2821290493011

php排序里的经典算法首先想到的就是冒泡排序法,

排序思想:两两交换小数上浮大数下沉每轮浮出一个最小数

代码如下

function maopao($arr,$length){
		$flag = true;
		$num = 0;
		for ($i=0; $i < $length-1&&$flag; $i++) { 
			$flag = false;
			for ($j=$length-2; $j >= $i; $j--) { 
				//从数组末尾开始比较交换
				if ($arr[$j]>$arr[$j+1]) {
					$flag = true;
					$temp = $arr[$j];
					$arr[$j] = $arr[$j+1];
					$arr[$j+1] = $temp;
					$num++;
				}
			}
		}
		echo "循环次数".$num."<br/>";
		echo "冒泡排序最终结果:".implode($arr,',')."<br/>";
	}

耗时测算:6.6322381496429

另一个经典的排序算法叫快速排序法,顾名思义这种排序方法排序非常快

排序思想:那一个数去跟数组中其他数做比较,比它小的放到左边,比它大的放到右边,这样递归查询最后得到的就是一个有序数组

代码如下:

function quicksort($arr,$length){
		if ($length<=1) {
			return $arr;
		}
		$left_arr = array();
		$right_arr = array();
		$basenum = $arr[0];
		for ($i=1; $i < $length; $i++) { 
			if ($basenum > $arr[$i]) {
				$left_arr[] = $arr[$i];
			}else{
				$right_arr[] = $arr[$i];
			}
		}
		//
		$left_arr = quicksort($left_arr,count($left_arr));
		$right_arr = quicksort($right_arr,count($right_arr));
		return array_merge($left_arr,array($basenum),$right_arr);
	}

耗时测算:0.075751066207886

可以看到相比较之前两种算法,快速排序法可以说是效率提升非常高的,不过后面有比快速排序法更快的排序方法

选择排序法

排序思想:选出最小数或最大数与第一位交换,然后再剩下的里边选出最小与第二位交换以此类推

代码如下:

function select($arr){
		$length = count($arr);
		//外层循环控制轮数
		for ($i=0; $i < $length; $i++) { 
			//假设$i的位置为最小数
			$p = $i;
			//内层循环选出最小值
			for ($j=$i+1; $j < $length; $j++) {
				//与$j进行比较 
				if($arr[$p]>$arr[$j]){
					$p = $j;
				}
			}
			//进行最小数交换
			$temp = $arr[$i];
			$arr[$i] = $arr[$p];
			$arr[$p] = $temp;
		}
		return $arr;
	}

耗时测算:3.2349390983582

插入排序法

排序思想:在要排序的一组数中,假设前面的数已经是排好顺序的,现在要把第n个数插到前面的有序数中,使得这n个数也是排好顺序的。如此反复循环,直到全部排好顺序

代码如下:

function insert($arr){
		$length = count($arr);
		//外层循环控制
		for ($i=1; $i < $length; $i++) { 
			for ($j=$i-1; $j >=0 ; $j--) { 
				if($arr[$j]>$arr[$j+1]){
					//交换
					$temp = $arr[$j];
					$arr[$j] = $arr[$j+1];
					$arr[$j+1] = $temp;
				}else{
					break;
				}
			}
			
		}
		return $arr;
	}

耗时测算:4.5077250003815

以上几种排序算法除快速排序法外都在3-6秒,可以说它们具有相同的时间复杂度,而它们都是采用的两层循环,所以它们的时间复杂度就是O(n²)。

而快速排序法采用一重循环,它的时间复杂度为O(nlogn),其中log指的是数学中的对数。

以上排序算法是PHP的基础知识

而我们项目中如果需要php对数组进行排序用那种排序方式呢,sort排序,没错就是php的sort函数

我们来测试一下sort的排序耗时:

    sort($arr);
    echo "sort排序最终结果:".implode($arr,',')."<br/>";

排序用时(秒):0.0046110153198242

比快速排序法还要高出一个数量级,至于sort排序的底层是怎么实现的,大牛们可以去研究一下内核

下面是不同的时间复杂度

排序时间复杂度.jpg