• 排序算法图解(五):快速排序分步刨析



    1 快速排序简介

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


    2 思路简介及图解

    快速排序算法通过多次比较和交换来实现排序,其排序流程如下:
    (1)首先设定一个分界值,通过该分界值将数组分成左右两部分。
    (2)将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边。此时,左边部分中各元素都小于分界值,而右边部分中各元素都大于或等于分界值。
    (3)然后,左边和右边的数据可以独立排序。对于左侧的数组数据,又可以取一个分界值,将该部分数据分成左右两部分,同样在左边放置较小值,右边放置较大值。右侧的数组数据也可以做类似处理。
    (4)重复上述过程,可以看出,这是一个递归定义。通过递归将左侧部分排好序后,再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后,整个数组的排序也就完成了。

    光看思路简介其实还不是很好理解,下面来举例说明

    一般情况下,我们会把数组中的一个数当作基准数(方便起见,会将数组最左边的当作基准数),然后从两边进行检索。按照如下步骤进行:

    • 先从右边检索比基准数小的
    • 再从左边检索比基准数大的
    • 一旦检索到,就停下,并将检索到的两个元素进行交换
    • 重复上述步骤,直到检索相遇,则替换基准数,并更新区间,递归进行
    • 最终序列会变得有序

    思路图解:

    该图出自网络,方便起见就以序列:{6,1,8,0,0,9,5,3,7} 为例子
    在这里插入图片描述
    具体分析一下第一趟排序:以6为基准数的步骤

    1. 红色块标识基准数,left、right初始位置如图所示:
      在这里插入图片描述

    2. right不断向左移动,寻找比基准数小的数,如图所示,找到了3
      在这里插入图片描述

    3. 此时left开始移动,不断向右移动,寻找比基准数大的数,找到了8,这时,left、right都找到了对应的数,进行交换:
      在这里插入图片描述

    4. right继续向左寻找比基准数6小的数,找到后,left继续向右寻找比基准数大的数,当left与right都找到对应的数后,再次进行交换。
      在这里插入图片描述

    5. 重复上述步骤,right继续向左走,但是此时,left与right相遇,指向了5的位置,则将基准数与该位置的数进行交换,这样就可以观察到,6的左边都是比6小的,右边都是比6大的。
      在这里插入图片描述

    6. 该过程需要递归进行,直到序列有序。即以5为基准数,递归6左边的区间,再递归右边的,反复进行,直到left >right退出。

    3 实现代码及运行结果

    import java.util.Arrays;
    
    /**
     * @author 兴趣使然黄小黄
     * @version 1.0
     * 快速排序
     */
    public class QuickSort {
    
        public static void main(String[] args) {
            int[] arr = {6,1,8,0,0,9,5,3,7};
            quickSort(arr, 0, arr.length-1);
            System.out.println("排序后: " + Arrays.toString(arr));
        }
    
        //快速排序
        public static void quickSort(int[] arr, int left, int right) {
            //边界条件
            if (left > right){
                return;
            }
    
            //定义基准数和左右指针
            int l = left;
            int r = right;
            int base = arr[left];
    
            //循环,将比基准数小的放在左边,比基准数大的放在右边
            while (l != r){
                //先从右边找比基准数小的,停下
                while (arr[r] >= base && l < r){
                    r--;
                }
                //从左边找比基准数大的,停下
                while (arr[l] <= base && l < r){
                    l++;
                }
                //此时已经找到对应的l 和 r,进行交换
                int temp = arr[l];
                arr[l] = arr[r];
                arr[r] = temp;
            }
            //至此,基准数两边都按照需要排好了,只需要将基准数与lr相遇的位置进行交换
            arr[left] = arr[l];
            arr[l] = base;
            //打印中间结果
            System.out.println(Arrays.toString(arr));
            //先向左找
            quickSort(arr, left, r-1);
            //向右递归
            quickSort(arr, l+1, right);
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53

    实现结果:
    在这里插入图片描述


    写在最后

    本文被 Java数据结构 收录点击订阅专栏 , 持续更新中。
     创作不易,如果你有任何问题,欢迎私信,感谢您的支持!

    在这里插入图片描述

  • 相关阅读:
    Python实验项目4 :面对对象程序设计
    [手写spring](3)初始化singletonObjects,实现依赖注入
    轻量容器引擎Docker基础使用
    XSS跨站脚本攻击
    Docker 笔记
    数据结构八种内部排序算法c++实现
    iOS视图控件的内容显示和离屏渲染流程
    PDF标准详解(一)——PDF文档结构
    springboot发送邮件
    Selenium自动化测试实战之自动化测试基础
  • 原文地址:https://blog.csdn.net/m0_60353039/article/details/127717659