排序算法PHP版

策略类

定义一系列的策略类,它们独立封装,并且遵循统一的接口

// 抽象策略接口
interface SortStrategy
{
    public function sort($arr);
}

冒泡排序

// 具体策略类
class BubbleStrategy implements SortStrategy
{
    public function sort($arr)
    {
        $len = count($arr);

        for ($i = 0; $i < $len - 1 ; $i++) {
            $flag = true;
            for ($j = 0; $j < $len - 1 - $i; $j++) {
                if ($arr[$j] > $arr[$j+1]) {
                    list($arr[$j], $arr[$j+1]) = array($arr[$j+1], $arr[$j]);
                    $flag = false;
                }
            }
            if ($flag) {
                break;
            }
        }

        return $arr;
    }
}

选择排序

class SelectStrategy implements SortStrategy
{
    public function sort($arr)
    {
        $len = count($arr);

        for ($i = 0; $i < $len - 1; $i++) { 
            $minIndex = $i;
            for ($j = $i + 1; $j < $len; $j++) { 
                if ($arr[$j] < $arr[$minIndex]) {
                    $minIndex = $j;
                }
            }
            if ($minIndex != $i) {
                list($arr[$i], $arr[$minIndex]) = array($arr[$minIndex], $arr[$i]);
            }
        }

        return $arr;
    }
}

插入排序

class InsertStrategy implements SortStrategy
{
    public function sort($arr)
    {
        $len = count($arr);

        for ($i = 1; $i < $len; $i++) { 
            $preIndex = $i - 1;
            $nowVal = $arr[$i];
            while ($preIndex >= 0 && $arr[$preIndex] > $nowVal) {
                $arr[$preIndex+1] = $arr[$preIndex];
                $preIndex--;
            }
            $arr[++$preIndex] = $nowVal;
        }

        return $arr;
    }
}

希尔排序

注意与插入排序的区别

class ShellStrategy implements SortStrategy
{
    public function sort($arr)
    {
        $len = count($arr);
        $gap = 1;
        while($gap < $len / 3) {
            $gap = $gap * 3 + 1;
        }

        for ($gap; $gap > 0; $gap = floor($gap / 3)) {
            for ($i = $gap; $i < $len; $i++) {
                $preIndex = $i - $gap;
                $nowVal = $arr[$i];
                while ($preIndex >= 0 && $arr[$preIndex] > $nowVal) {
                    $arr[$preIndex+$gap] = $arr[$preIndex];
                    $preIndex -= $gap;
                }
                $arr[$preIndex+$gap] = $nowVal;
            }
        }

        return $arr;
    }
}

归并排序

class MergeStrategy implements SortStrategy
{
    public function sort($arr)
    {
        $len = count($arr);
        if ($len < 2) {
            return $arr;
        }
        $mid = floor($len / 2);
        $left = array_slice($arr, 0, $mid);
        $right = array_slice($arr, $mid);
        return $this->merge($this->sort($left), $this->sort($right));
    }

    private function merge($left, $right)
    {
        $res = [];

        while (count($left) > 0  && count($right) > 0) {
            if ($left[0] <= $right[0]) {
                $res[] = array_shift($left);
            } else {
                $res[] = array_shift($right);
            }
        }

        while (count($left) > 0) {
             $res[] = array_shift($left);
        }

        while (count($right) > 0) {
             $res[] = array_shift($right);
        }

        return $res;
    }
}

快速排序

class QuickStrategy implements SortStrategy
{
    public function sort($arr)
    {
        $len = count($arr);
        if ($len < 2) {
            return $arr;
        }
        $mid = $arr[0];
        $left = [];
        $right = [];

        for ($i = 1; $i < $len; $i++) { 
            if ($arr[$i] > $mid) {
                $right[] = $arr[$i];
            } else {
                $left[] = $arr[$i];
            }
        }

        $left = $this->sort($left);
        $right = $this->sort($right);

        return array_merge($left, [$mid], $right);
    }
}

堆排序

class HeapStrategy implements SortStrategy
{
    private $len = 0;

    public function sort($arr)
    {
        $this->len = count($arr);
        $this->buildMaxHeap($arr);
        for ($i = $this->len - 1; $i > 0; $i--) {
            list($arr[0], $arr[$i]) = array($arr[$i], $arr[0]);
            $this->len--;
            $this->heapify($arr, 0);
        }
        return $arr;
    }

    public function buildMaxHeap(&$arr)
    {
        for ($i = floor($this->len/2) - 1; $i >= 0 ; $i--) { 
            $this->heapify($arr, $i);
        }
    }

    public function heapify(&$arr, $i)
    {
        $left = 2 * $i + 1;
        $right = 2 * $i + 2;
        $bigIndex = $i;

        if ($left < $this->len && $arr[$left] > $arr[$bigIndex]) {
            $bigIndex = $left;
        }

        if ($right < $this->len && $arr[$right] > $arr[$bigIndex]) {
            $bigIndex = $right;
        }

        if ($bigIndex != $i) {
            list($arr[$bigIndex], $arr[$i]) = array($arr[$i], $arr[$bigIndex]);
            $this->heapify($arr, $bigIndex);
        }
    }
}

计数排序

class CountingStrategy implements SortStrategy
{
    public function sort($arr)
    {
        $maxVal = max($arr);
        $minVal = min($arr);
        for ($i = $minVal; $i <= $maxVal; $i++) { 
            $bucket[] = 0;
        }

        foreach ($arr as $v) {
            $bucket[$v]++;
        }

        $newIndex = 0;
        while ($newIndex < count($arr)) {
            if ($bucket[$minVal] != 0) {
                $arr[$newIndex++] = $minVal;
                $bucket[$minVal]--;
            } else {
                $minVal++;
            }
        }

        return $arr;
    }
}

环境类

用来管理策略,实现不同策略的切换功能

// 环境角色类
class Role
{
    private $sortStrategy;

    public function __construct(SortStrategy $sortStrategy)
    {
        $this->sortStrategy = $sortStrategy;
    }

    public function asc($array)
    {
        return $this->sortStrategy->sort($array);
    }

}

客户端

通过给予不同的具体策略,获取结果

// 客户端代码
$arr = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0];

$role = new Role(new MergeStrategy());
$data = $role->asc($arr);

$role = new Role(new QuickStrategy());
$data = $role->asc($arr);

设计模式仅用来参考、理解其思想,实际中不同策略类返回不同结果

评论

暂无评论