画江湖之算法篇 [排序算法] 快速排序

算法篇

1 快速排序简介

概括:

  • 快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。
    小伙伴们仔细看下面的动态图哦

完整代码块

public static function quick($arr){
        if(count($arr)<=1){
            return $arr;
        }

        $k=$arr[0];
        $x=array();
        $y=array();
        $_size=count($arr);
        for($i=1;$i<$_size;$i++){
            if($arr[$i]<=$k){
                $x[]=$arr[$i];
            }elseif($arr[$i]>$k){
                $y[]=$arr[$i];
            }
        }
        $x=Sort::quick($x);
        $y=Sort::quick($y);
        return array_merge($x,array($k),$y);
    }

2 分析代码块 具体分析到代码注释哦 ~

快速排序

public static function quick($arr){
        if(count($arr)<=1){ //如果数组根本就一个元素就直接返回 不用在排序咯
            return $arr;
        }

        $k=$arr[0];//定义一个初始要排序的值 默认为数组第一个
        $x=array();//定义比要排序的值 小的数组块
        $y=array();//定义比要排序的值 大的数组块
        $_size=count($arr);//统计数组的大小
        for($i=1;$i<$_size;$i++){//循环数组 记住这边要从索引1 开始
            if($arr[$i]<=$k){//如果当前的值小于 要排序的值
                $x[]=$arr[$i];//就把小于的值放到 小的数组块中
            }elseif($arr[$i]>$k){//如果当前的值大于 要排序的值
                $y[]=$arr[$i];//就把大于的值放到 大的数组块中
            }
        }
        $x=Sort::quick($x);//依次递归执行 这样就会得到小的数组块
        $y=Sort::quick($y);//依次递归执行 这样就会得到大的数组块
        return array_merge($x,array($k),$y);//最后在合并下 小的模块+中间的模块【初始要排序的值】+大的模块 就ok~
    }
    // print_r(Sort::quick($arr));

3 时间复杂度 分析

file

本作品采用《CC 协议》,转载必须注明作者和本文链接
《L04 微信小程序从零到发布》
从小程序个人账户申请开始,带你一步步进行开发一个微信小程序,直到提交微信控制台上线发布。
《L02 从零构建论坛系统》
以构建论坛项目 LaraBBS 为线索,展开对 Laravel 框架的全面学习。应用程序架构思路贴近 Laravel 框架的设计哲学。
讨论数量: 1

关于快排的稳定性 我有个疑问。快速排序理论上可以选取任意一点作为pivot,我写的实现方式和楼主一样,一般我们都是取头或者取尾作为pivot的,不考虑空间复杂度消耗使用array_merge的话 快速排序就是稳定算法了,楼主能给个不稳定的例子么

4年前 评论

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!