php实现基础算法

冒泡排序

算法思想：第一个数与第二个比较，第二个数与第三个数比较，第三个数与第四个比较....直到末尾 ,每次比较前一个数大就与后面的数交换位置。
例如：数组[1,2,-1,-3,5,-8,10] 元素从小到大排序
第一趟比较，需要比较6次
第一个数与第二个数比较 [1,2,-1,-3,5,-8,10],
第二个数与第三个数比较[1,-1,2,-3,5,-8,10],
第三个数与第四个数比较[1,-1,-3,2,5,-8,10],
第四个数与第五个数比较[1,-1,-3,2,5,-8,10],
第五个数与第六个数比较[1,-1,-3,2,-8,5,10],
第六个数与第七个数比较[1,-1,-3,2,-8,5,10],
结果：[1,-1,-3,2,-8,5,10]

第二趟比较 需要比较4次
第一个数与第二个数比较 [-1,1,-3,2,-8,5,10],
第二个数与第三个数比较[-1,-3,1,2,-8,5,10],
第三个数与第四个数比较[-1,-3,1,2,-8,5,10],
第四个数与第五个数比较[-1,-3,1,-8,2,5,10],
结果：[-1,-3,1,-8,2,5,10]

第三趟比较 需要比较3次
第一个数与第二个数比较 [-3,-1,1,-8,2,5,10],
第二个数与第三个数比较[-3,-1,1,-8,2,5,10],
第三个数与第四个数比较[-3,-1,-8,1,2,5,10],
结果：[-3,-1,-8,1,2,5,10]
.....
依次类推

规律：每进行一趟比较都会把前面最大的数排到数组的后面，每趟要进行比较的次数为数组的长度减1再减趟数。

function bufferSort($arr)
{
    $l = count($arr);
    for($i=0;$i<$l;$i++) //趟数循环
    {
          //每趟要比较的次数
         for($j=0;$j<$l-1-$i;$j++)
        {
            if($arr[$j] > $arr[$j+1])
            {
               //如果前一个数比后一个数大那么交换两个数的位置
                $temp = $arr[$j];
                $arr[$j] = $arr[$j+1];
                $arr[$j+1] = $temp;
            }
        }
    }
  return $arr;
}  

选择排序

算法思想:把数组切成左边和右边两个部分，默认左边部分为数组的第一个元素，其他的为右边部分。因为默认第一个元素是最小的值，然后从右边的元素中筛选做小的值与左边的元素进行比较，如果左边的数值大，就与之交换位置。
第一次循环都会把第一最小值排在第一位
第二次循环都会把第二最小值排在第二位
第三次循环都会把第二最小值排在第三位
依次类推

//选择排序
function selectSort(array $arr)
{
    $temp = 0;
    $l = count($arr);
    for($i=0;$i<$l;$i++)
    {
        $minVal = $arr[$i];//默认第一个就是最小的元素
        $minIndex = $i;//记录一下最小元素的位置
        //在数组剩下的元素中找一个最小的，跟$minVal比较
        for($j=$i+1;$j<count($arr);$j++)
        {
            //如果$minVal不是最小的，那么记录这个最小值以及它的index
            if($minVal > $arr[$j])
            {
                $minVal = $arr[$j];
                $minIndex = $j;
            }
        }
        //通过上面的for循环能找出最小的元素，以及最小元素对应的index
        //交换位置
        $temp = $arr[$i];
        $arr[$i] = $minVal;
        $arr[$minIndex] = $temp;
    }
    return $arr;
}

插入排序

算法思想：也是把数组划分左，右两部分，左边部分为排好序的，默认第一个元素是最小的而且是排好序的。往后逐个元素与左边的元素进行比较，然后放到适当的位置。（从右边依次拿一个元素与左边的元素一一比较）
例如：数组[1,-2,3]
默认第一个是最小有序的左边 1 右边是-2，3
-2与1比较 结果是 [-2,1,3] 左边变成-2，1 右边 3
然后3与左边的元素进行比较 结果[-2.1,3]

//插入排序
function insertSort(array $arr)
{
    $l=count($arr);
    for($i=1; $i<$l; $i++) {
        //默认第一个是有序最小的
        //需要从第二个元素开始进行与第一个进行比较
        $tmp = $arr[$i];//需要拿去跟左边比较的元素
        //内层循环 与左边元素比较
        for($j=$i-1; $j>=0; $j--) {
            if($tmp < $arr[$j]) {
                //在左边找到比较元素的插入的位置
                $arr[$j+1] = $arr[$j];
                $arr[$j] = $tmp;
            } else {
                //如果碰到不需要移动的元素
                //由于是已经排序好是数组，则前面的就不需要再次比较了。
                break;
            }
        }
    }
    return $arr;
}

性能对比

插入排序 > 选择排序 > 冒泡排序