PHP四种基础排序算法--冒泡,直接插入,快速和选择排序


冒泡排序:重复的走访要排序的数列,一次比较2个元素,如果他们的顺序错误则交换过来,这样重复进行到没有需要再交换。该排序方法名称的由来指小(或者大的)的元素会经由交换慢慢的浮到数列的前端。

function maopao(&$array)

{     

     $temp=array();

     //第一层循环,控制需要冒泡的轮数

     for($i=1,$len=count($array);$i<$len;$i++){

          //第二层循环,控制冒出一个数需要经历的轮数

          for($j=0;$j<$len-$i;$j++){

               if($array[$j]>$array[$j+1]){

                   $temp=$array[$j+1];

                   $array[$j+1]=$array[$j];

                   $array[$j]=$tmp;   

               }

          }

     }

     return $array;

}


直接插入排序:每次从无序列表中取出第一个元素,把他插入到有序列表的合适位置,使表仍然有序

算法实现:第一趟比较前两个数,然后把第二个数按大小插入到有序表中; 第二趟把第三个数据与前两个数从后向前扫描,把第三个数按大小插入到有序表中;依次进行下去,进行了(n-1)趟扫描以后就完成了整个排序过程。

直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序是将待比较的数值与它的前一个数值进行比较,所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较,直到找到比待比较数值小的并将待比较数值置入其后一位置,结束该次循环。

function insertSort(&$array)

{

     $tmp=array();

     //双重循环,外层控制轮数,内层控制比较次数

     //从第二个数值开始

     for($i=1,$len=count($array);$i<$len;$i++){

        $temp=$array[$i];     //设置哨兵(待比较数),假设该数前面的数都已经完成排序。

        //当前一位数值大于待比较数时,继续循环      

        for($j=$i-1;$j>=0 & $array[$j]>$temp;$j--){

                 $array[$j+1]=$array[$j];     //将比较后的数值往后挪一位

        }

        $array[$j+1]=$temp;     //当找到比待比较数小的数值时,在该数值后面以为插入待比较数          

     }

     return $array;

}


插入排序和冒泡排序很类似,但是冒泡排序是比较2个相邻的数值的大小,通过2个数不断的比较而达到排序的目的,而直接插入排序是从后往前比较第n+1个数在前n个已经排序的数中的位置,并插入其中。二者的时间复杂度都是O(n^2).

快速排序:选择当前数组中任意一个元素(一般为第一个元素)作为标准,将后面的元素与标准元素比较,比标准元素小的放入一个数组,否则放入另一个数组,然后再对这两个数组进行同样的操作,该排序方法一般使用递归实现

function FastSort($arr){

     //判断递归是否该需要进行

    if(count($arr) <= 1) {

        return $arr;

    }

    $base_num=$arr[0];     //选取第一个元素作为标准元素

    $left_arr=array();     //比标准元素小的元素装入这个数组

    $right_arr=array();     //比标准元素大的元素装入该数组

    for($i=1;$i<count($arr);$i++){

        if($arr[$i]<$base_num){

            $left_arr[]=$arr[$i];

          }else{

            $right_arr[]=$arr[$i];

          }

     }

     $left_arr=FastSort($left_arr);

     $right_arr=FastSort($right_arr);

     return array_merge($left_arr,array($base_num),$right_arr);

}


选择排序:在要排序的一组数中,选出最小的一个数与第一个位置的数交换。然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止。

function selectSort($arr) {

//双重循环完成,外层控制轮数,内层控制比较次数

 $len=count($arr);

    for($i=0; $i<$len-1; $i++) {

        //先假设最小的值的位置

        $p = $i;

        for($j=$i+1; $j<$len; $j++) {

            //$arr[$p] 是当前已知的最小值

            if($arr[$p] > $arr[$j]) {

            //比较,发现更小的,记录下最小值的位置;并且在下次比较时采用已知的最小值进行比较。

                $p = $j;

            }

        }

        //已经确定了当前的最小值的位置,保存到$p中。如果发现最小值的位置与当前假设的位置$i不同,则位置互换即可。

        if($p != $i) {

            $tmp = $arr[$p];

            $arr[$p] = $arr[$i];

            $arr[$i] = $tmp;

        }

    }

    //返回最终结果

    return $arr;

}


书山有路勤为径 学海无涯苦作舟