网站首页技术博客

    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."
";
		echo "一般排序最终结果：".implode($arr,',')."
";
	}

这个算法耗时怎么样呢，这里利用随机数生成一个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."
";
		echo "冒泡排序最终结果：".implode($arr,',')."
";
	}

耗时测算：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,',')."
";

排序用时（秒）：0.0046110153198242

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