PHP 常用排序算法

fdwe2e

排序算法

<?php
namespace iphp\algorithm;
/**
* Created by PhpStorm.
* User: 123
* Date: 14-9-3
* Time: 下午3:53
*/
class Sort
{

    /**
     * 冒泡排序
     * 算法，相邻２个元素比较，如果前大于后者，交换位置
     * 第一次比较，将最大的元素排在了最后。
     * 需要n-1次冒泡
     * @param $arr
     * @return mixed
     */
    public static function bubble($arr)
    {
        $num=count($arr);
        if($num<=1)
            return $arr;

        //些标识用于判断如果有一次没有经过交换。那么不需要再进行下一次循环
        $flag=false;
        for($i=0;$i<$num-1;$i++)
        {
           for($j=0;$j<$num-1-$i;$j++)
           {
               //交换元素
               if($arr[$j]>$arr[$j+1])
               {
                   $tmp=$arr[$j];
                   $arr[$j]=$arr[$j+1];
                   $arr[$j+1]=$tmp;
                   $flag=true;
               }
           }
           if($flag==false)
               break;
        }
        return $arr;
    }

    /**
     * 选择排序
     * 第一次，取每1-n个元素之间的最小值，与第０个元素比较，并将最小的放在前面。
     * @param $arr
     * @return mixed
     */
    public static function select($arr)
    {
        $num=count($arr);
        if($num<=1)
            return $arr;

        for($i=0;$i<$num-1;$i++)
        {
            $minValue=$arr[$i];
            $minIndex=$i;
            for($j=$i+1;$j<$num;$j++)
            {
                if($minValue>$arr[$j])
                {
                    $minValue=$arr[$j];
                    $minIndex=$j;
                }
            }

            //交换位置
            if($i!=$j)
            {
                $tmp=$arr[$i];
                $arr[$i]=$minValue;
                $arr[$minIndex]=$tmp;
            }
        }
        return $arr;
    }

    /**
     * 插入排序
     * 最开始将数组的第一个元素当作已经排序的数组。将后面的元素与已排好序的比较，将其插入到已排序中的适当位置。
     * @param $arr
     * @return mixed
     */
    public static function insert($arr)
    {
        $num=count($arr);
        if($num<=1)
            return $arr;

        for($i=1;$i<$num;$i++)
        {
            $insertValue=$arr[$i];
            $insertIndex=$i-1;
            while($insertIndex>=0 && $insertValue<$arr[$insertIndex])
            {
                $arr[$insertIndex+1]=$arr[$insertIndex];
                $insertIndex--;
            }
            $arr[$insertIndex+1]=$insertValue;
        }

        return $arr;
    }

    /**
     * 快速排序
     * @param $arr
     * @return array
     */
    public static function quick($arr)
    {
        $num=count($arr);
        if($num<=1)
            return $arr;
        $middle=$arr[0];
        $leftArr=array();
        $rightArr=array();
        for($i=1;$i<$num;$i++)
        {
            if($arr[$i]<=$middle)
                $leftArr[]=$arr[$i];
            else
                $rightArr[]=$arr[$i];
        }
        $leftArr=self::quick($leftArr);
        $rightArr=self::quick($rightArr);
        return array_merge($leftArr,array($middle),$rightArr);
    }
}