排序算法，以php为代码示例

2021-05-17 00:27

阅读：432

标签：示例 partition 快速排序 phpstorm func creat UNC [] src

一、冒泡排序

/**
 * Created by PhpStorm.
 * User: 郑楚周
 * Date: 2018/9/28
 * Time: 16:10
 *//**冒泡排序
 * Class Bubble
 */
class Bubble implements sort
{
    /**冒泡排序
     * @param $arr
     */
    public function sort($arr)
    {
        $count = count($arr);
        if($count 
        for($i = ($count - 2); $i >= 0; $i--) {
            for ($j = 0; $j                 if($arr[$j] > $arr[$j+1]) {
                    $tmp = $arr[$j];
                    $arr[$j] = $arr[$j+1];
                    $arr[$j+1] = $tmp;
                }
            }
        }
        return $arr;
    }
}
二、选择排序

/**
 * Created by PhpStorm.
 * User: 郑楚周
 * Date: 2018/9/28
 * Time: 16:10
 *//**选择排序
 * Class Select
 */
class Select implements sort
{
    public function sort($arr)
    {
        $count = count($arr);
        for ($i = 0; $i             $minIndex = $i;
            for ($j = $i + 1; $j                 if ($arr[$minIndex] > $arr[$j]) {
                    $minIndex = $j;
                }
            }
            helper::swap($arr[$i], $arr[$minIndex]);
        }
        return $arr;
    }
}
三、插入排序

/**
 * Created by PhpStorm.
 * User: 郑楚周
 * Date: 2018/10/5
 * Time: 16:43
 *//**插入排序
 * Class Insert
 */
class Insert implements sort
{
    /**版本1
     * @param $arr
     * @return mixed
     */
/*    public function sort($arr)
    {
        $count = count($arr);
        for ($i = 1; $i             for ($j = $i; $j > 0 && $arr[$j]                 helper::swap($arr[$j], $arr[$j - 1]);
            }
        }
        return $arr;
    }*/
    /**版本2
     * @param $arr
     * @return mixed
     */
    public function sort($arr)
    {
        $count = count($arr);
        for ($i = 1; $i             $tmp = $arr[$i];
            for ($j = $i; $j > 0 && $tmp                 $arr[$j] = $arr[$j - 1];
            }
            $arr[$j] = $tmp;
        }
        return $arr;
    }
}
四、归并排序

/**
 * Created by PhpStorm.
 * User: 郑楚周
 * Date: 2018/10/5
 * Time: 19:26
 *//**归并排序
 * Class Merge
 */
class Merge implements sort
{
    /**自上向下归并排序
     * @param $arr
     */
    public function sort($arr)
    {
        $this->__mergeSort($arr, 0, count($arr) - 1);
        return $arr;
    }
    /**自下向上归并排序
     * @param $arr
     */
    public function sortBu($arr)
    {
        $count = count($arr);
        for ($sz = 1; $sz             for ($i = 0; $i                 $this->__merge($arr, $i, $i + $sz - 1, helper::min($i + 2*$sz - 1, $count - 1));
            }
        }
        return $arr;
    }
    private function __mergeSort(&$arr, $left, $right)
    {
        if ($left >= $right) {
            return;
        }
        $mid = floor(($left + $right)/2);
        $this->__mergeSort($arr, $left, $mid);
        $this->__mergeSort($arr, $mid + 1, $right);
        if ($arr[$mid] > $arr[$mid + 1])
            $this->__merge($arr, $left, $mid, $right);
    }
    /**将$arr[$left]~$arr[$mid]和$arr[$mid + 1]~$arr[$right]两部分进行归并
     * @param $arr
     * @param $left
     * @param $mid
     * @param $right
     */
    private function __merge(&$arr, $left, $mid, $right)
    {
        $tmpArr = [];
        for ($i = $left; $i             $tmpArr[$i] = $arr[$i];
        }
        $i = $left;
        $j = $mid + 1;
        for ($k = $left; $k             if ($i > $mid) {
                $arr[$k] = $tmpArr[$j];
                $j++;
            } elseif ($j > $right) {
                $arr[$k] = $tmpArr[$i];
                $i++;
            } elseif ($tmpArr[$i]                 $arr[$k] = $tmpArr[$i];
                $i++;
            } else {
                $arr[$k] = $tmpArr[$j];
                $j++;
            }
        }
    }
}


五、快速排序

/**
 * Created by PhpStorm.
 * User: 郑楚周
 * Date: 2018/10/6
 * Time: 11:02
 */
class Quick implements sort
{
    /**
     * @param $arr
     * @return mixed
     */
    public function sort($arr)
    {
        $this->__quick($arr, 0, count($arr) - 1);
        return $arr;
    }    /**
     * @param $arr
     * @param $l
     * @param $r
     */
    private function __quick(&$arr, $l, $r)
    {
        if ($l >= $r)
            return;
        $p = $this->__partition($arr, $l, $r);
        $this->__quick($arr, $l, $p);
        $this->__quick($arr, $p + 1, $r);
    }
    /**遍历$l+1到$r,每个值和$l的值比较，将数值小的放在数组左侧，大的放在右侧，最后在将$l对应的值和$j对应的值交换位置
     * @param $arr
     * @param $l
     * @param $r
     * @return mixed
     */
    private function __partition(&$arr, $l, $r)
    {
        $v = $arr[$l];
        $j = $l;
        for ($i = $l + 1; $i             if ($arr[$i]                 helper::swap($arr[$i], $arr[++$j]);
        }
        helper::swap($arr[$l], $arr[$j]);
        return $j;
    }
}
六、排序效率对比如下