(九)Java算法:快速排序(详细图解)

这篇具有很好参考价值的文章主要介绍了(九)Java算法:快速排序(详细图解)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、前言

1.1、概念

   快速排序:用数组的第一个数作为基准数据,然后将所有比它小的数都放到它左边,所有比它大的数都放到它右边,这个过程称为一趟快速排序。值得注意的是,快速排序不是一种稳定的排序算法,也就是说,多个相同的值的相对位置也许会在算法结束时产生变动。

1.2、算法过程

  1. 数组为arr,设置两个变量leftright,排序开始的时候:left=0,right=arr.length-1
  2. 以第一个数组元素作为关键数据,赋值给key,即key=A[left]
  3. right开始向前搜索,即从后向前搜索(right–),找到第一个小于key的值 arr[right],将 arr[right]arr[left] 的值交换,如果不满足(即3中arr[right]不小于key),则right=right-1
  4. left开始向后搜索,即从前向后搜索(left++),找到第一个大于keyarr[left],将arr[left]arr[right] 的值交换,如果不满足(即4中arr[left]不大于key),则left=left+1
  5. 重复第3、4步,直到left==right (3,4步中,找到符合条件的值,进行交换的时候leftright指针位置不变。另外,left==right 时循环结束)

二、maven依赖

pom.xml

<dependencies>
    <dependency>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter</artifactId>
        <version>2.6.0</version>
    </dependency>

    <dependency>
        <groupId>org.projectlombok</groupId>
        <artifactId>lombok</artifactId>
        <version>1.16.14</version>
    </dependency>
</dependencies>

三、流程解析

  假设我们要排序的数据是:19, 28, 8, 23, 10, 21, 9

3.1、全部数据分区

  先看看全部数据分区是怎么做的,后续递归过程和这个是一样的。

(九)Java算法:快速排序(详细图解)

  我们找的基准值是要分区的数组的首个元素:arr[left]=arr[0]=19,你也可以选其他的位置,比如中间,或者尾部,因为我们选的是首部,那么开始遍历的位置就是从右边开始,这个很重要哦。经过我们的分区之后,19左边的元素都比19要小,19右边的数据都比19要大

3.2、左边数据分区

  左边部分分区过程如下:

(九)Java算法:快速排序(详细图解)

  左边分区的数据都是全部数据分区的基准值19左边的元素,不涉及到19右边的元素,找的基准值是分区的数组的首个元素:9。经过我们的分区之后,9左边的元素都比9要小,9右边的数据都比9要大

3.3、右边数据分区

  右边部分分区过程如下:

(九)Java算法:快速排序(详细图解)
  右边分区的数据都是全部数据分区后的基准值19右边的元素,不涉及到19左边的元素,同样找的基准值是要分区的数组的首个元素:23。经过我们的分区之后,23左边的元素都比23要小,23右边的数据都比23要大。实际以为我们目前的数据来说,数组已经是有序的了。

四、编码实现

  上面我们演示了一个基本的流程,如果数据更多,就继续按照左边和右边继续分区,实际上就是一个递归。我们看看具体的实现就懂了。

    public static void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            log.info("开始排从【arr[{}]】到【arr[{}]】数据", left, right);
            int pivot = partition(arr, left, right);
            log.info("返回的基准位置是:{},分区排序后的结果:{}", pivot, arr);
            // 基准元素一定比左边的数大,所以左边分区最大值是:pivot - 1,分区范围是[left, pivot - 1]
            quickSort(arr, left, pivot - 1);
            // 基准元素一定比右边的数小,所以右边分区最小值是:pivot + 1,分区范围是[pivot + 1, right]
            quickSort(arr, pivot + 1, right);
        }
    }

    public static int partition(int[] arr, int left, int right) {
        // 定义基准元素
        int pivotValue = arr[left];
        // 遍历(条件就是分区左边索引小于右边索引)
        while (left < right) {
            // 从右边right开始遍历,找到一个数比基准数小
            while (left < right && arr[right] >= pivotValue) {
                // 未找到,继续往前找
                right--;
            }
            // 找到了,则把找到小值放到此时左边索引的位置
            // 第一次进入时,基准元素已存放到临时值pivotValue了,第一次就相当于放到基准位置了,同时,arr[right]也腾出了一个位置
            arr[left] = arr[right];
            // 从左边left开始遍历,找到一个数比基准数大
            while (left < right && arr[left] <= pivotValue) {
                // 未找到,继续往后找
                left++;
            }
            // 找到了,则把找到大值放到此时右边索引的位置(也就是腾出的位置)
            // 同时,arr[left]也腾出了一个位置
            arr[right] = arr[left];
        }
        // left等于right说明遍历结束了,把基准元素插入到腾出的位置,也就是arr[left]或者arr[right]
        arr[left] = pivotValue;
        // 返回基准元素插入的位置
        return left;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{19, 28, 8, 23, 10, 21, 9};
        log.info("要排序的初始化数据:{}", arr);
        //从小到大排序
        quickSort(arr, 0, arr.length - 1);
        log.info("最后排序后的结果:{}", arr);
    }

运行结果:

要排序的初始化数据:[19, 28, 8, 23, 10, 21, 9]
开始排从【arr[0]】到【arr[6]】数据
返回的基准位置是:3,分区排序后的结果:[9, 10, 8, 19, 23, 21, 28]
开始排从【arr[0]】到【arr[2]】数据
返回的基准位置是:1,分区排序后的结果:[8, 9, 10, 19, 23, 21, 28]
开始排从【arr[4]】到【arr[6]】数据
返回的基准位置是:5,分区排序后的结果:[8, 9, 10, 19, 21, 23, 28]
最后排序后的结果:[8, 9, 10, 19, 21, 23, 28]

结语

  只要懂了前面三个部分的分区,那么你理解这个快速排序就容易了,相信我的图已经给你很好的启示了。文章来源地址https://www.toymoban.com/news/detail-497629.html

到了这里,关于(九)Java算法:快速排序(详细图解)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 图解快排——快速排序算法(quick sort)

    算法思想 快速排序算法是对冒泡排序算法的一种改进算法,在当前所有内部排序算法中,快速排序算法被认为是最好的排序算法之一。 快速排序的基本思想: 通过一趟排序将待排序的序列分割为左右两个子序列,左边的子序列中所有数据都比右边子序列中的数据小,然后对

    2024年01月16日
    浏览(37)
  • 排序算法进阶——归并排序【详细图解,递归和非递归】

    在了解归并排序之前让我们先了解一下归并这一算法吧! 归并算法一般应用于合并两个已经有序的序列,使合并后的序列也有序,是一个时间复杂度为O(N)的算法,不过一般要借助两个要排序的序列的元素个数个额外的空间。 一一一一一一一一一一一一一一一一一一一一一

    2024年01月24日
    浏览(45)
  • 【JAVA】七大排序算法(图解)

    稳定性: 待排序的序列中若存在值相同的元素,经过排序之后,相等元素的先后顺序不发生改变,称为排序的稳定性。 思维导图: (排序名称后面蓝色字体为 时间复杂度和稳定性 ) 核心思路 每次从无序区间中选择第一个元素,插入到有序区间的合适位置,直到整个数组有

    2024年02月12日
    浏览(36)
  • 【算法与数据结构】归并排序的代码实现(详细图解)以及master公式的讲解

    目录 1、归并排序  1.1、算法描述  1.2、图解说明 2、代码实现  3、master公式 3.1、公式以及结论 3.2、适用于某些特殊的递归 3.3、计算归并排序的时间复杂度 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用 递归 或者说是 分治法 (Divide and Conquer)的一个非

    2024年02月08日
    浏览(62)
  • 七大排序算法——冒泡排序,通俗易懂的思路讲解与图解(完整Java代码)

    排序:所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 上述待排序的数中,有两个5。 将 前面 的5标记一个a, 将 后面 的5标记一个b。 通过算法进行排序后,这一组数就有序了, 但是要看两个相同的5的位置是否有改变。

    2024年02月16日
    浏览(39)
  • 七大排序算法——归并排序,通俗易懂的思路讲解与图解(完整Java代码)

    排序:所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 上述待排序的数中,有两个5。 将 前面 的5标记一个a, 将 后面 的5标记一个b。 通过算法进行排序后,这一组数就有序了, 但是要看两个相同的5的位置是否有改变。

    2024年02月15日
    浏览(46)
  • 七大排序算法——希尔排序,通俗易懂的思路讲解与图解(完整Java代码)

    排序:所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 上述待排序的数中,有两个5。 将 前面 的5标记一个a, 将 后面 的5标记一个b。 通过算法进行排序后,这一组数就有序了, 但是要看两个相同的5的位置是否有改变。

    2024年02月03日
    浏览(52)
  • 七大排序算法——堆排序,通俗易懂的思路讲解与图解(完整Java代码)

    排序:所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 上述待排序的数中,有两个5。 将 前面 的5标记一个a, 将 后面 的5标记一个b。 通过算法进行排序后,这一组数就有序了, 但是要看两个相同的5的位置是否有改变。

    2024年02月16日
    浏览(34)
  • 快速排序算法C++实现(超详细解析!!!!)

    目录 一、前言 (1)分治算法 (2)分治算法解题方法     1.分解:     2.治理:     3.合并: 二、快速排序 1.问题分析 2.算法设计     (1)分解:     (2)治理 :     (3)合并:     (4)基准元素的选取: 3.算法分析 三、AC代码  四、共勉     快速排序,其实是一种

    2024年02月03日
    浏览(41)
  • 【排序算法】 快速排序(快排)!超详细看这一篇就够了”保姆级教学“

    🎥 屿小夏 : 个人主页 🔥个人专栏 : 算法—排序篇 🌄 莫道桑榆晚,为霞尚满天! 什么是快排?快排的速度到底有多快呢?它们的思想和实现是什么样的? 本文会对这快速排序进行详解,绝对细致入微!让你彻底搞懂快排! 英国计算机科学家Tony Hoare在1960年为了解决计算

    2024年02月05日
    浏览(54)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包