快速排序【Java算法】

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

1. 概念

快速排序是一种比较高效的排序算法,采用 “分而治之” 的思想,通过多次比较和交换来实现排序,在一趟排序中把将要排序的数据分成两个独立的部分,对这两部分进行排序使得其中一部分所有数据比另一部分都要小,然后继续递归排序这两部分,最终实现所有数据有序。

2. 思路

① 给出一组待排序序列,我们取该序列的第一个元素为基准值。什么是基准值?就是相当于参考物吧。接着再取两个哨兵,什么是哨兵?暂且当它为指针吧;

② 那么这个序是怎么个排法?首先,我们在序列的最左边和最右边各放一个哨兵,我们分别称它们为 left 和 right,left 从左往右走寻找比基准值大的数,right 从右往左走寻找比基准值小的数

规定第一步应该让 right 先迈出,我们让它一直往左走,走到什么地步?直到它找到了比基准值小的数为止,就停下来。right 停下来之后,就轮到 left 走了,同样道理,当 left 找到了比基准值大的数时,它也停了下来,left 和 right 都停了,接下来,交换这两个位置的数值,第一轮互相奔赴的旅途结束;

④ 第一轮结束后,还有下一轮,现在它们两个都停在半路上,没有见到彼此,路途遥远继续走。同样的方法,left 继续 ++ 向右走,right- - 向左走,满足条件时等待双方都停下来,交换数值,交换完继续走;

⑤ 以上所有的奔赴过程,我们都通过 while 循环来实现。其中,外层 while 循环控制双方交换完数值之后继续奔赴,退出条件就是 left 和 right 相撞的那一刻。内层两个 while 循环控制它们各自从一个停止点到另一个停止点的行走过程,退出条件是找到下一个停止点的时候。相当于外层循环发号施令,说开始走,于是内层循环听到了指令,就让 left 和 right 各自走到了自己的下一个停止位置,交换数值之后,静等外层循环的指令,才可以再到下一个目标点;

⑥ 当 left == right 时,循环结束,我们把 left 和 right 相遇位置的数值与基准值互换一下,此时,整体上基准值左边的数均小于基准值右边的数,但是左右两边各自的排序是乱的;

⑦ 道理是一样的,此时我们可以从基准处将序列分为两部分,然后用递归的方法排序这两部分,最终实现所有数据有序排列

3. 代码实现

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] arr = {3, 2, 9, 11, 17, 4, 13, 7, 5, 1, 12};
        int[] newArr = quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(newArr));
    }

    public static int[] quickSort(int[] arr, int low, int high) {
        if (low > high) {
            return arr;
        }
        int base = arr[low];
        int left = low;
        int right = high;
        while (left != right) {
            while (arr[right] >= base && left < right) {
                right--;
            }
            while (arr[left] <= base && left < right) {
                left++;
            }
            int temp;
            temp = arr[right];
            arr[right] = arr[left];
            arr[left] = temp;
        }
        arr[low] = arr[left];
        arr[left] = base;
        quickSort(arr, low, left - 1);
        quickSort(arr, right + 1, high);
        return arr;
    }
}

快速排序【Java算法】,算法合集,java,算法,排序算法文章来源地址https://www.toymoban.com/news/detail-629827.html

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

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

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

相关文章

  • Java实现快速排序

    一.原理 快速排序算法通过多次比较和交换来实现排序,其排序流程如下:   (1)首先设定一个分界值,通过该分界值将数组分成左右两部分。  (2)将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边。此时,左边部分中各元素都小于分界值,而右

    2024年02月09日
    浏览(40)
  • 快速排序Java

    快速排序是在工具类常用的排序算法,快速排序的思想主要是选定一个基准元素,然后找到基准元素的位置,然后再分别排序他左边的和他右边的,快速排序是不稳定的,时间复杂度位Nlog(N),最极端的情况就是一个反向排好顺序的数组,然后每次二分都分不开导致的时间复杂度

    2024年02月08日
    浏览(30)
  • 【JAVA】快速排序

    快排,和冒泡排序一样,是同一类型的排序,都是交换排序 交换,涉及在遍历中比较,然后相互交换元素 冒泡排序是根据趟数两两比较,边比较边交换,快排也一样,不过冒泡是以顺序表的格式进行的,而快排则是建立在二叉树的基础上来完成遍历交换的~(个人理解) 快排

    2024年02月01日
    浏览(29)
  • 快速排序(java代码)

    快排核心思想就是:首先在待排序数组中随便选择一个数作为节点(pivot),然后从最后面(high)往左查找比这个节点(pivot)小的数,并且从最前面(low)往右查找比这个节点(pivot)大的数(low),情况1:找到后就把这两个数进行交换,然后接着上面的查找交换直到low等

    2024年02月12日
    浏览(39)
  • Java 快速排序

    快速排序是一种常用的基于比较的排序算法,其时间复杂度为 O(nlogn),并且具有稳定性和广泛的应用场景。本文将全面详细的讲解一下 Java 中快速排序算法的原理、实现以及时间复杂度等问题。 快速排序是一种分治思想的排序算法,其基本原理可以概括为以下三步: 选取一

    2024年02月10日
    浏览(47)
  • Java基础(十一)快速排序

    快速排序的思想 快速排序(QuickSort)是一种高效的排序算法,基于分治策略。它的原理可以概括为以下步骤: 选择一个基准元素(pivot),通常选择数组中的一个元素作为基准。这个基准元素将用来将数组分割为较小和较大的两个子数组。 分区过程(Partition):将数组中的

    2024年02月13日
    浏览(38)
  • 随机化快速排序(Java 实例代码)

    一、概念及其介绍 快速排序由 C. A. R. Hoare 在 1960 年提出。 随机化快速排序基本思想: 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进

    2024年02月11日
    浏览(37)
  • 插入、希尔、归并、快速排序(java实现)

    目录 插入排序 希尔排序 归并排序 快速排序 插入排序 排序原理: 1.把所有元素分为两组,第一组是有序已经排好的,第二组是乱序未排序。 2.将未排序一组的第一个元素作为插入元素,倒序与有序组比较。 3.在有序组中找到比插入元素小或者大的元素,将插入元素放入该位

    2024年02月13日
    浏览(39)
  • Java 七大排序之快速排序(三种方法包含优化方法)

    任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。 1)  挖坑法 划分完之后,再左右递归。

    2024年02月09日
    浏览(39)
  • 第三十三章Java快速排序法

            快速排序 (Quicksort)是对 冒泡排序 的一种改进,是一种排序执行效率很高的排序算法。         快速排序的基本思想是:通过一趟排序,将要排序的数据分隔成独立的两部分,其中一部分的所有数据比另外一部分的所有数据都要小,然后再按此方法对这两部分

    2024年02月11日
    浏览(54)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包