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

冷环渊

发布于 2022-01-26 08:36:17

2760

发布于 2022-01-26 08:36:17

文章被收录于专栏：冷环渊的全栈工程师历程冷环渊的全栈工程师历程

前言

★ 这里是小冷的博客 ✓ 优质技术好文见专栏个人公众号，分享一些技术上的文章，以及遇到的坑当前系列：数据结构系列源代码 git 仓库 ‘ 数据结构代码地址代码Git 仓库地址

目录
前言
快速排序
思路分析
快速排序案例
排序过程断点调试
快速排序测速

快速排序

快速排序法介绍：

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

思路分析

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

首先是找到一个基准点，这个不一定非要是中位数，也可以是任意一位，可以自主分割，在什么位置都可以，这里我们以中位来学习
根据中位数为基准，将需要排序的数组分为两份，之后分别交换位置，保证比中位数小的都在左边，比中位数的都在右边，此时左右两边虽然无序，但是都保证一定规则
之后按照递归，再次将左边选出中位数，右边选出中位数，递归到不能交换为止

快速排序案例

要求: 对 [-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);
        }
    }