在PHP中已经有现成的函数帮助我们为数组排序，那我们还有必要去自己实现为数组排序的算法吗？有的。我们知道其实 程序 = 数据结构 + 算法，可见算法在我们程序中是非常关键的组成部分，好的算法可以让程序的执行效率更高，占用空间更少。 举个例子，我们写一个计算1+2+3+4+……+999+1000的程序，方法1我们可以先计算1+2 = 3，然后计算3+3 = 6，然后计算6+4 = 10 ，然后 10+5 =15 …… 计算999次，最后得到结果。方法2我们可以使用中学学过的等差数列求和公式Sn=n(a1+an)/2 ， 直接计算1000 * （1+1000）/ 2 得到结果，使用方法2的程序只需计算1次，就能得到结果，所以效率更高。这就是算法的作用和魅力所在。 下面我们通过排序算法了解计算机是怎么为我们的数组排序的，去入门算法。 ***注：为方便描述，下面的排序全为正序（从小到大排序）*** ## 一、冒泡排序 假设有一个数组[a,b,c,d] 冒泡排序依次比较相邻的两个元素，如果前面的元素大于后面的元素，则两元素交换位置；否则，位置不变。具体步骤： 1，比较a,b这两个元素，如果a>b,则交换位置，数组变为：[b,a,c,d] 2，比较a,c这两个元素，如果a<c,则位置不变，数组变为：[b,a,c,d] 3，比较c,d这两个元素，如果c>d,则交换位置，数组变为：[b,a,d,c] 完成第一轮比较后，可以发现最大的数c已经排（冒）在最后面了，接着再进行第二轮比较，但第二轮比较不必比较最后一个元素了，因为最后一个元素已经是最大的了。 第二轮比较结束后，第二大的数也会冒到倒数第二的位置。 依次类推，再进行第三轮，，， 就这样最大的数一直往后排（冒），最后完成排序。所以我们称这种排序算法为冒泡排序。 ``` $arr = [9,4,7,1,8,6,3,10,2]; function bubbleSort($arr) { $len = count($arr); //该层循环轮数 for ($i = 1; $i < $len; $i++) { //该层依次比较相邻的两个数 for ($k = 0; $k < $len - $i; $k++) { //如果前面的元素大于后面的元素，调换位置： if ($arr[$k] > $arr[$k + 1]) { $tmp = $arr[$k + 1]; // 声明一个临时变量 $arr[$k + 1] = $arr[$k]; $arr[$k] = $tmp; } } } return $arr; } $arr = bubbleSort($arr); print_r($arr); ``` [](http://static.tscgo.cn/FqxVzMJAcsXdL2X_Mh7Zb55kry4- ) ## 二、选择排序 选择排序是一种直观的算法，每一轮会选出列中最小的值，把最小值排到前面。具体步骤如下: 1. 第一轮，先把数组中的第一个元素作为最小值，最小值的位置（索引）保存在一个变量$min中 2. 接着拿第二个元素与我们初始设定的最小值比较，如果第二个元素比最小值小，那么$min的值变为第二个元素的位置（索引），否则，不做处理。 3. 接着同样的去拿最新的最小值与第三个元素比较，与第四个，第五个，，，到最后，这得到的$min就是数组中的最小值, 然后把最小值与第一个元素交换位置，至此，第一轮循环结束。 4，用同样的方法进行第二轮查找，找到第二个最小值，与第二个元素交换位置；然后第三个，第四个，直至排序完成 ``` $arr = [9,4,7,1,8,6,3,10,2]; //实现思路 双重循环完成，外层控制轮数，当前的最小值。内层控制比较次数 function selectSort($arr) { $len = count($arr); //$i 当前最小值的位置， 需要参与比较的元素 for ($i = 0; $i < $len - 1; $i++) { //先假设最小的值的位置 $min = $i; //所以$arr[$min] 是 当前已知的最小值 //$j 当前都需要和哪些元素比较，$i 后边的。 for ($j = $i + 1; $j < $len; $j++) { //比较，发现更小的,记录下最小值的位置；并且在下次比较时，应该采用已知的最小值进行比较。 $min = ($arr[$min] <= $arr[$j]) ? $min : $j; } //已经确定了当前的最小值的位置，保存到$min中。 //如果发现 最小值的位置与当前假设的位置$i不同，则位置互换即可 if ($min != $i) { $tmp = $arr[$min]; $arr[$min] = $arr[$i]; $arr[$i] = $tmp; } } return $arr; } $arr = selectSort($arr); print_r($arr); ``` [](http://static.tscgo.cn/FnIk7W1x-duXiavH5UO9hZPSnvjs ) ## 三、插入排序 插入排序步骤大致如下： 1. 先定义第一个元素为有序数列，第二个元素与第一个元素相比，如果第二元素小于第一个元素，则把第二个元素插到第一个元素的前面，否则，顺序不变。如此，第一个元素和第二个元素就组成了一个新的有序数列 2. 第三个元素与前面所述的有序数列比较，如果第三个元素小于第二个元素，则第三个元素再与第一个元素比较，如果第三个元素大于第一个元素，那么第三个元素就插入到第一二元素中间，此时有序数列变成了三个元素。 3. 如此重复，进行第四个，第五个，第六个，，，元素到排序 ```` //插入排序 $arr = [9,4,7,1,8,6,3,10,2]; function insertSort($arr) { $len=count($arr); for($i=1; $i<$len; $i++) { //获得当前需要比较的元素值 $tmp = $arr[$i]; //内层循环控制 比较 并 插入 for($j=$i-1; $j>=0; $j--) { //$arr[$i];需要插入的元素 //$arr[$j];需要比较的元素 if($tmp < $arr[$j]) { //发现插入的元素要小，交换位置 //将后边的元素与前面的元素互换 $arr[$j+1] = $arr[$j]; //将前面的数设置为 当前需要交换的数 $arr[$j] = $tmp; } else { //如果碰到不需要移动的元素 //由于是已经排序好是数组，则前面的就不需要再次比较了。 break; } } } //将这个元素 插入到已经排序好的序列内。 //返回 return $arr; } $arr = insertSort($arr); print_r($arr); ```` [](http://static.tscgo.cn/FqLiqBKJMFtJpO2_isSHKt2_xpLk ) ## 四、快速排序 快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来，且在大部分真实世界的数据，可以决定设计的选择，减少所需时间的二次方项之可能性。 步骤： 从数列中挑出一个元素，称为 “基准”（pivot）， 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。 ```` //快速排序 $arr = [9,4,7,1,8,6,3,10,2]; function quickSort($arr) { //判断参数是否是一个数组 if(!is_array($arr)) return false; //递归出口:数组长度为1，直接返回数组 $length = count($arr); if($length<=1) return $arr; //数组元素有多个,则定义两个空数组 $left = $right = array(); //使用for循环进行遍历，把第一个元素当做比较的对象 for($i=1; $i<$length; $i++) { //判断当前元素的大小 if($arr[$i] < $arr[0]){ //从小到大 < || 从大到小 > $left[]=$arr[$i]; }else{ $right[]=$arr[$i]; } } //递归调用 $left=quickSort($left); $right=quickSort($right); //将所有的结果合并 return array_merge($left,array($arr[0]),$right); } $arr = quickSort($arr); print_r($arr); ```` [](http://static.tscgo.cn/FkJnEZ2xXYytIZYHQPFZhp_PyHAS ) 至此，PHP实现常见的排序算法已经完成，代码也有相应的注释，希望对大家有帮助。