在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

二、选择排序

选择排序是一种直观的算法，每一轮会选出列中最小的值，把最小值排到前面。具体步骤如下:

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);

选择排序.gif

三、插入排序

插入排序步骤大致如下：

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);

插入排序.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