阅读 153

刷抖音?不如来学算法,几分钟搞定一个快速排序

快速排序是一种高效的排序算法,也是面试常考的一种算法,大多数人畏惧和逃避算法,不是因为算法有多难,而是没有找到合适的老师,简单说就是没有通俗易懂的文章,导致学习者越看越懵,看完即忘的现象。今天我想尝试做一个“好老师”,用通俗易懂的方式讲解一下什么是快速排序。

图解思想

很多文章,上来就用某种语言,开始啪啦啪啦写代码,不熟悉该种语言的学者,一脸蒙蔽,又是一篇水文。或者跟着代码看了一下,感觉会了,关掉网页,脑子:what???我刚才看了啥?

算法与编程语言无关,它是一种思想,理解了思想,编程语言只是一种实现方式。

OK,来看看快速排序的思想

假设现在有一个乱序的数组:

5 3 6 1 4 8 2 7
复制代码

快速排序核心思想:

随意找一个目标值,放在数组的某个下标,使得该下标的左侧数值都小于目标值,右侧数值都大于目标值

随意选一个目标值,假如就数组的第一个数值 5,现在需要将 5 移动到数组的某个下标 K 上,并且以 K 为临界点,左边的数小于 5 ,右边的数大于 5 ,该怎么操作?

使用一种二分交换的思想,以什么分?以下标 K 分。需要解决2个问题,如何交换数值,如何确定下标 K

如何交换?

模拟两个人,从数组 5 3 6 1 4 8 2 7 两边开始探测,先从右往左开始找一个小于5的数,再从左往右找一个大于5的数,然后交换数据,交换完成继续探测,直到两个人相遇

模拟的两个人暂且称它们为:"探子j""探子i"

开始时,"探子j" 站在 右边"探子i" 站在 左边

在这里插入图片描述
由于我们选了最左边的数为 基准数,所以要从右边的 "探子j" 先出发,这个很重要(原因等你看完整个思路,自己模拟从左边开始试试就知道哪里出错了) "探子j" 一步步向左移动(j- -)寻找小于 5 的数字,找到 2 满足,停下来。再出动 "探子i" 一步步向右移动(i++)寻找大于5的数字,找到 6 满足,停下来。此时 "探子i" 停在6上,"探子j" 停在2上,然后交换 i 和 j 的数值
在这里插入图片描述
到这里完成了第一次交换,数组变化:

5 3 6 1 4 8 2 7 => 5 3 2 1 4 8 6 7

在现有的位置上继续探测,还是从 "探子j" 开始(强调,每次都是从探子j开始),继续向左移动(j- -),找到 4 满足,停下来;然后 "探子i" 开始继续往右寻找,走到 4 没有找到大于 5 的数字两个人就相遇了。(如果相遇之前能找到满足的数值,则依旧交换这两个值)

在这里插入图片描述

如何确定下标 K

当两个探子相遇的下标位置,就是下标 K,此时将下标 K 数值与之前选择的 基准数 相互交换,实现 K 的左边都小于基准数,右边大于基准数

在这里插入图片描述
到这一步,我们确定了临界点 K,并且实现 K 左边的数小于 基准数 ,右边的数大于 基准数。得到数组:

4 3 2 1 5 8 6 7

以 K (5) 做分界点,将数组分为两个部分,然后将左右两边的子数组在执行上述操作,最终将整个数组完成排序

OK,以上就是快速排序的基本思想,应该可以理解吧。

撸码实现算法

理解了思想,就按照这算法的思想一步步写代码就行了,本人熟悉java,就用java作为编程语言撸一遍

 	/**
     * 快速排序
     *
     * @param array 目标数组
     * @param left  数组最左下标值
     * @param right 数组最右下标值
     */
    public static void quickSort(int[] array, int left, int right) {

        //防止数组越界(这一步最后再回来理解)
        if (left >= right) return;

        int base = array[left];//基准数
        int i = left, j = right;//左探子i,右探子j
        int temp;//用于交换的临时变量

        while (i != j) {//两个探子相遇前

            //找出小于 基准数 的下标,当大于等于 基准数 的时候,探子j 向左移动即可(j--)
            while (array[j] >= base && i < j) {
                j--;
            }

            //找出大于 基准数 的下标,当小于等于 基准数 的时候,探子i 向右移动即可(i++)
            while (array[i] <= base && i < j) {
                i++;
            }

            //经过上面两个循环之后,探子j,探子i 都会停在符合条件的值的下标上面,然后就可以进行交换值啦
            if (i < j) {
                temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }

        //经过上面的循环之后会触发 i=j 的条件(即两个探子相遇),此时将基准值的数与i或者j(随便哪个都一样)下标的值交换,完成一次交换探测
        array[left] = array[i];//基准值的位置
        array[i] = base;//基准值

        //完成交换之后再对左右两边的子数组进行递归调用走上面的方法,完成整个数组的排序
        quickSort(array, left, i - 1);//左边
        quickSort(array, i + 1, right); //右边
    }
复制代码

读注释!读注释!读注释!然后就是,使用快排算法排序数组

        int[] array = new int[]{5, 3, 6, 1, 4, 8, 2, 7};
        quickSort(array, 0, array.length - 1);//快速排序
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");//打印排序后的数组
        }
复制代码

结果输出

1 2 3 4 5 6 7 8 
复制代码
关注下面的标签,发现更多相似文章
评论