十大经典排序算法:快速排序debug分析排序过程

简介: 十大经典排序算法:快速排序debug分析排序过程

快速排序

快速排序法介绍:


快速排序(Quicksort)是对冒泡排序的一种改进。基本思想是:通过一趟排序将要排序的数据分割成独立的两 部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排 序,整个排序过程可以递归进行,以此达到整个数据变成有序序列


思路分析

1.png


快速排序的思路由上图所示:


首先是找到一个基准点,这个不一定非要是中位数,也可以是任意一位,可以自主分割,在什么位置都可以,这里我们以中位来学习

根据中位数为基准,将需要排序的数组分为两份,之后分别交换位置,保证比中位数小的都在左边,比中位数的都在右边,此时左右两边虽然无序,但是都保证一定规则

之后按照递归,再次将左边选出中位数,右边选出中位数,递归到不能交换为止

2.png


快速排序案例

要求: 对 [-9,78,0,23,-567,70] 进行从小到大的排序,要求使用快速排序法。【测试 8w 和 800w】 说明[验证分析]:


如果取消左右递归,结果是 -9 -567 0 23 78 70


如果取消右递归,结果是 -567 -9 0 23 78 70


如果取消左递归,结果是 -9 -567 0 23 70 78


public static void quickSort(int[] arr, int left, int right) {
        //  left index
        int l = left;
        int r = right;
        //    pivot 中轴值
        int pivot = arr[(left + right) / 2];
        //临时变量
        int temp = 0;
        //    while 循环的目的是比比中轴的pivot值小的放在左边
        //    比pivot 值大的放在右边
        while (l < r) {
            //    在pivot的左边一直寻找 找到大于等于pivot 的值才退出
            while (arr[l] < pivot) {
                l += 1;
            }
            //    在pivot的右边一直寻找 找到小于等于pivot 的值才退出
            while (arr[r] > pivot) {
                r -= 1;
            }
            //    如果 l>=r说明pivot的左右两个值已经按照左边全都是小于等于pivot,右边去哪不是大于等于pivot排列好了
            if (l >= r) {
                break;
            }
            //    交换
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
            //    如果交换玩发现这个arr[l]==pivot值 相等r--前移
            if (arr[l] == pivot) {
                r -= 1;
            }
            //如果交换玩发现 arr[r] == pivot值 相等l++ 后移
            if (arr[r] == pivot) {
                l += 1;
            }
        }
        //    如果l==r 必须是 l++ r-- 否则会出现栈溢出
        if (l == r) {
            l += 1;
            r -= 1;
        }
        //向左递归
        if (left < r) {
            quickSort(arr, left, r);
        }
        //向右递归
        if (right > l) {
            quickSort(arr, l, right);
        }
    }

排序过程断点调试

int arr[] = {-9, 78, 0, 23, -567};


我们的测试数组是一个五位数的数组,

1.png



进入循环,此时我们看到,中位数和左右两边的索引,0和4


这里我们可以看第一组数据,


下标0 arr[l] =- 9, -9小于0于是 左边下标后移继续寻找,找到78,此时l = 1 是78对应的数组下标 此时的78 比中位 0 要大,进入右侧比对

1.png



显然 arr[r] = -567 比中位数小,不需要改变下标,跳出循环,


此时我们对比因为我们之后需要重复的递归,这里就是我们递归的跳出条件,如果左边大于右边了,代表左边已经没有大于中位数的数了,反之右边也一定没有小于中位数的

10.png



此时,交换两边不符合条件的数字,将比0大的七十八交换到右边吗,将比0小的-567交换到左边

10.png



交换完成之后,判断左右两边此时小标的数字是否与中位数相等,如果相等就后移,不需要重复比对


此时我们的第一次循环就结束了,可以看到,数组已经被交换到了,我们的思路第一步的样子,


比中位数0 小的都在左边,比中位数0大的都在右边,之后我们需要重复递归,一直到交换不了为止

10.png



此时 r 与l相等,就代表都到中位数了,左右两边都递归有序了,此时我们需要将l后一位,r前移一位,防止栈溢出,并且再继续向下,再最后一次递归之前会结束,

10.png



后面的递归就是重复的分组重复的交换,一直到左索引小于又索引,代表还可以继续分组排序,直到左边递归完毕


右索引大于左索引代表可以继续向右边递归,一直到右边递归完毕

10.png



快速排序测速

八十万长度存放0-80w的随机数

10.png



可以看到,效率是十分的快速

10.png



有兴趣的小伙伴可以自己试试写一个冒泡排序测试一下,再拿小冷的快速排序测试一下,算法的精妙之处一下就能感受到了


相关文章
|
7天前
|
机器学习/深度学习 算法 安全
【无人机三维路径规划】基于非支配排序的鲸鱼优化算法NSWOA与多目标螳螂搜索算法MOMSA求解无人机三维路径规划研究(Matlab代码实现)
【无人机三维路径规划】基于非支配排序的鲸鱼优化算法NSWOA与多目标螳螂搜索算法MOMSA求解无人机三维路径规划研究(Matlab代码实现)
|
8天前
|
机器学习/深度学习 运维 算法
基于非支配排序遗传算法NSGAII的综合能源优化调度(Matlab代码实现)
基于非支配排序遗传算法NSGAII的综合能源优化调度(Matlab代码实现)
基于非支配排序遗传算法NSGAII的综合能源优化调度(Matlab代码实现)
|
9天前
|
机器学习/深度学习 算法 安全
【无人机三维路径规划】多目标螳螂搜索算法MOMSA与非支配排序的鲸鱼优化算法NSWOA求解无人机三维路径规划研究(Matlab代码实现)
【无人机三维路径规划】多目标螳螂搜索算法MOMSA与非支配排序的鲸鱼优化算法NSWOA求解无人机三维路径规划研究(Matlab代码实现)
|
1月前
|
机器学习/深度学习 算法 安全
【无人机3D路径规划】基于非支配排序遗传算法NSGAII的无人机3D路径规划研究(Matlab代码实现)
【无人机3D路径规划】基于非支配排序遗传算法NSGAII的无人机3D路径规划研究(Matlab代码实现)
127 1
|
16天前
|
机器学习/深度学习 算法 安全
【微电网】【创新点】基于非支配排序的蜣螂优化算法NSDBO求解微电网多目标优化调度研究(Matlab代码实现)
【微电网】【创新点】基于非支配排序的蜣螂优化算法NSDBO求解微电网多目标优化调度研究(Matlab代码实现)
|
1月前
|
机器学习/深度学习 算法 安全
【优化调度】基于matlab非支配排序遗传算法求解车辆充电调度优化问题研究(Matlab代码实现)
【优化调度】基于matlab非支配排序遗传算法求解车辆充电调度优化问题研究(Matlab代码实现)
|
5天前
|
供应链 算法 Java
【柔性作业车间调度问题FJSP】基于非支配排序的多目标小龙虾优化算法求解柔性作业车间调度问题FJSP研究(Matlab代码实现)
【柔性作业车间调度问题FJSP】基于非支配排序的多目标小龙虾优化算法求解柔性作业车间调度问题FJSP研究(Matlab代码实现)
|
3月前
|
机器学习/深度学习 边缘计算 算法
NOMA和OFDMA优化算法分析
NOMA和OFDMA优化算法分析
239 127
|
10天前
|
存储 算法 搜索推荐
软考算法破壁战:从二分查找到堆排序,九大排序核心速通指南
专攻软考高频算法,深度解析二分查找、堆排序、快速排序核心技巧,对比九大排序算法,配套动画与真题,7天掌握45%分值模块。
52 0
软考算法破壁战:从二分查找到堆排序,九大排序核心速通指南
|
5月前
|
数据采集 机器学习/深度学习 算法
别急着上算法,咱先把数据整明白:大数据分析的5个基本步骤,你都搞对了吗?
别急着上算法,咱先把数据整明白:大数据分析的5个基本步骤,你都搞对了吗?
229 4

热门文章

最新文章