排序算法(快排&归并&选择&插入&冒泡)php&go实现

Z时代
2024-01-10
分类：综合
//排序常用算法
//排序算法 稳定排序算法
class SortAlg
{
    //冒泡排序
    public function maoPaoSort($arr)
    {
        $n = count($arr);
        if ($n <= 1) {
            return $arr;
        }
        for ($i=0; $i < $n; $i++) {
            //退出循环比较标识符
            $flg = false;
            for ($j = 0; $j < $n - 1; $j++) {
                //冒泡是一种稳定排序 遇到相等的值时 不用交换位置 直接退出比较循环
                if ($arr[$j] > $arr[$j + 1]) { //数据交换
                    $tmp = $arr[$j + 1];
                    $arr[$j+1] = $arr[$j];
                    $arr[$j] = $tmp;
                    $flg = true; //有数据交换
                }
            }
            //没有数据交换
            if (!$flg) {
                break;
            }
        }
        return $arr;
    }
    //插入排序 稳定排序算法
    //是在排好序的数据中做值的对比和移动
    public function insertSort($arr)
    {
        $n = count($arr);
        if ($n <= 1) {
            return $arr;
        }
        for ($i = 1; $i < $n; $i++) {
            $val = $arr[$i]; //第二个位置
            for ($j= $i - 1; $j >= 0; $j--) {
                //依次比较前面数据每一个数据是否大于当前$arr[$i],如果大于
                //则 往后位置移动, $j最后为要插入数据的位置
                if ($arr[$j] > $val) {
                    $arr[$j + 1] = $arr[$j];
                } else {
                    break;
                }
            }
            //最后要插入位置插入当前值 $j为-1时 位置为第一个(0)
            $arr[$j + 1] = $val;
        }
        return $arr;
    }
    //选择排序 非稳定排序算法
    //是在未排序的数据中做比较 找到最小值的位置 然后交换最小值与当前值
    public function selectSort($arr)
    {
        $n = count($arr);
        if ($n <= 1) {
            return $arr;
        }
        $tmp = 0;
        for ($i = 0; $i < $n - 1; $i++) {
            $min = $i; //最小数位置
            for ($j = $i + 1; $j < $n; $j++) {
                if ($arr[$j] < $arr[$min]) {
                    $min = $j;
                }
            }
            //交换 最小值与当前值交换
            if ($min != $j) {
                $tmp = $arr[$i];
                $arr[$i] = $arr[$min];
                $arr[$min] = $tmp;
            }
        }
        return $arr;
    }
    //归并排序 稳定排序 分而治之
    public function mergeSort($arr)
    {
        $n = count($arr);
        if ($n <= 1) {
            //递归结束条件
            return $arr;
        }
        $mid = intval($n / 2);
        $l = array_slice($arr, 0, $mid);
        $r = array_slice($arr, $mid);
        $left = $this->mergeSort($l); //左边数据拆分
        $right = $this->mergeSort($r); //右边数据拆分
        $ret = $this->Merge($left, $right);
        return $ret;
    }
    //合并
    private function Merge($left, $right)
    {
        $arr = [];
        $i = 0;
        while (count($left) && count($right)) {
            //此处相当于正在移动左右指针
            if ($left[$i] < $right[$i]) {
                $arr[] = array_shift($left);
            } else {
                $arr[] = array_shift($right);
            }
        }
        return array_merge($arr, $left, $right);
    }
    //快速排序 但是这种不是原地排序 $left和$right需要额外申请空间
    public function quickSort1($arr)
    {
        $n = count($arr);
        if ($n <= 1) {
            //递归结束条件
            return $arr;
        }
        $left = [];
        $right = [];
        $mid = array_pop($arr);
        foreach ($arr as $k => $v) {
            if ($arr[$k] < $mid) {
                $left[] = $v;
            } else {
                $right[] = $v;
            }
        }
        $l = $this->quickSort1($left);
        $r = $this->quickSort1($right);
        return array_merge($l, [$mid], $r);
    }
    //快速排序 原地排序 移动指针排序 不用申请其他空间
    public function quickSort2()
    {
    }
}
$arr = [7, 5, 6, 3, 8, 2, 4];
$sort = new SortAlg;
//冒泡排序
// var_dump($sort->maoPaoSort($arr));exit;
//插入排序
// var_dump($sort->insertSort($arr));
//选择排序
// var_dump($sort->selectSort($arr));
//归并排序
// var_dump($sort->mergeSort($arr));
//快速排序
var_dump($sort->quickSort1($arr));