在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);
冒泡排序.gif
二、选择排序
选择排序是一种直观的算法，每一轮会选出列中最小的值，把最小值排到前面。具体步骤如下:
- 第一轮，先把数组中的第一个元素作为最小值，最小值的位置（索引）保存在一个变量$min中
- 接着拿第二个元素与我们初始设定的最小值比较，如果第二个元素比最小值小，那么$min的值变为第二个元素的位置（索引），否则，不做处理。
- 接着同样的去拿最新的最小值与第三个元素比较，与第四个，第五个，，，到最后，这得到的$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);
选择排序.gif
三、插入排序
插入排序步骤大致如下：
- 先定义第一个元素为有序数列，第二个元素与第一个元素相比，如果第二元素小于第一个元素，则把第二个元素插到第一个元素的前面，否则，顺序不变。如此，第一个元素和第二个元素就组成了一个新的有序数列
- 第三个元素与前面所述的有序数列比较，如果第三个元素小于第二个元素，则第三个元素再与第一个元素比较，如果第三个元素大于第一个元素，那么第三个元素就插入到第一二元素中间，此时有序数列变成了三个元素。
- 如此重复，进行第四个，第五个，第六个，，，元素到排序
//插入排序
$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);
插入排序.gif
四、快速排序
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 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);
快速排序.gif
网友评论