首页 > 编程语言 >三路快排Java版(带思路分析)

三路快排Java版(带思路分析)

时间:2023-05-25 10:12:02浏览次数:39  
标签:Rt arr Java int ++ 快排 Lt 三路

快速排序

这里我们直接开始讲相对的最优解 带随机数的三路快排 好了,中间还有很多版本的快排,但是都有一些问题导致在某种极端情况下造成耗费时间极多。

  • 基础快排:在序列本身有序的情况下复杂度为O(n²)

  • 带随机数的快排:在序列本身有序的情况下复杂度为O(nlogn),但是在序列全部元素相同情况下复杂度为O(n²)

  • 带随机数的双路快排:比前者更快一些为O(n),因为前后同时向中间遍历,但是在序列全部元素相同情况下的复杂度问题仍旧未解决

  • 带随机数的三路快排: 解决上述各种问题且时间复杂度最快O(n)

工作原理:

将数组分为三个部分,小于V的,等于V的,大于V的。

  1. 首先在数组中选取任意一个下标和最左边的下标互换(选取一个随机下标的目的是,将快排结果最后V左边或右边没有东西的极端情况概率降到最小甚至约等于0,如果出现这种情况将会导致复杂度为n²,这里我们不再深入讨论)

  2. 确定需要的变量:因此我们要有2个下标 Lt,Rt 将数组分割成3部分。还需要一个下标 i 指向当前的元素 e 。除此之外,用 l 和 r 确定数组的首尾。

  3. 分配当前元素 e 去哪个区域 这里我们又分为3种情况:

    1. e < V 将e和Lt+1处(也就是 ==V 的第一个元素)的位置交换,然后Lt++

    2. e == V 将e直接纳入该区域(也就是不做处理)然后 i++ 即可

    3. e > V 将e和Rt - 1处(也就是 >V 的前一个元素)的位置交换,然后Rt--

    无论是哪个情况,无非就是将其和Lt和Rt附近的元素交换位置即可。

image-20230523124958793

  1. 那么当全部都排序完毕时,也就是鼠标指的那个点处,i 和 Rt 重合时,退出循环

image-20230523130418720

  1. 因为按顺序应该是 小于V ,V,==V,>V ,所以只要将V和 <V 处的最后一个元素交换位置即可

image-20230523130852762

6.最后反复递归调用 <V 区间以及 >V 的区间,从而让两边的区间也都有序。

实现一下吧:

package com.sort;
import java.util.Random;
​
/**
 * @Author: 翰林猿
 * @Description: 三路快排
 **/
public class Quick {
    public Quick() {
    }
​
    public static <T extends Comparable<T>> void quicksort(T[] arr) {
        Random random = new Random();
        quicksort3ways(arr, 0, arr.length - 1, random);
    }
​
    private static <T extends Comparable<T>> void quicksort3ways(T[] arr, int l, int r, Random random) {
        if (l >= r)
            return;
        int randomInt = random.nextInt(r + 1 - l);      //生成一个不超过数组长度的随机数
        swap(arr, randomInt, l);                                 //把他和首元素交换位置
        //定义需要的变量
        int Lt = l;
        int Rt = r + 1;
        int i = Lt + 1;
        while (i < Rt) {
            if (arr[i].compareTo(arr[l]) < 0) {
                Lt++;                               //因为应该交换Lt+1处,所以可以直接先++再交换
                swap(arr, Lt, i);
                i++;
            } else if (arr[i].compareTo(arr[l]) == 0) {
                i++;
            } else if (arr[i].compareTo(arr[l]) > 0) {
                Rt--;                               //因为应该交换Rt-1处,所以可以直接先--再交换
                swap(arr, Rt , i);
                i++;
            }
        }
        swap(arr,l,Lt);                             //将V摆到小于V和等于V中间
        quicksort3ways(arr,l,Lt-1,random);       //反复递归调用 <V 区间以及 >V 的区间,让这两区间也都有序
        quicksort3ways(arr,Rt,r,random);
    }
​
    public static <E> void swap(E[] arr, int j, int beforej) {
        E t = arr[j];
        arr[j] = arr[beforej];
        arr[beforej] = t;
    }
}
​

 

 

标签:Rt,arr,Java,int,++,快排,Lt,三路
From: https://www.cnblogs.com/hanlinyuan/p/17430325.html

相关文章

  • Cannot run program “G:\Java\bin\java.exe“ (in directory “C:\compile-serve
    今夜拾起两年前早已遗忘的java踌躇满志打开idea发现早已物是人非他报错了,然鹅并没有解决,解决方法我把Structure里多余的jdk删掉,只剩下jdk1.8,如图,就解决了......
  • java易错题锦集系列五
    接口中不能有构造方法,抽象类中可以有。抽象类中构造方法作用:初始化抽象类的成员;为继承它的子类使用定义在同一个包(package)内的类是可以不经过import而直接相互使用final修饰的方法可以被重载但不能被重写从设计层面来说,抽象类是对类的抽象,是一种模板设计,接口是行为的抽象,是一种行......
  • java易错题锦集四
    effectivejava不要再构造方法中启动任何线程g=newGameServer();g.start();构造器无返回值,但是不能void修饰字符串String是包装类型吗?答案:不是对应的基本类型和包装类如下表:基本数据类型包装类byteBytebooleanBooleanshortShortcharCharacterintIntegerlongLon......
  • java易错题锦集二
    源码补码inti=5;intj=10;System.out.println(i+~j);有个公式,-n=~n+1另一种解题思路~代表对n按位取反10的源码是:0000000000000000000000001010所以对10按位取反就是1111111111111111111111110101由于计算机中-1表示为1111111111111111111111111111显然......
  • MQTT入门DEMO(Java语言)
    目录快速开始准备下载及安装第一次安装EMQX第一次运行EMQX客户端代码快速开始准备MQTT简介EMQX简介下载及安装第一次安装EMQX版本选择EMQX支持多种操作系统,请选择合适您的版本下载。下载地址:https://www.emqx.io/cn/downloads#broker在MicrosoftWindows下安装目前EMQX......
  • java输出乘法口诀
    importjava.util.StringTokenizer;publicclassImoocStudent{publicstaticvoidmain(Stringargs[]){for(inti=1;i<9;i++){for(intj=1;j<=i;j++){System.out.print(j+"*"+i+"=&q......
  • JAVA-两个日期比较大小
    packagecom.swift.ksv5;importjava.util.Date;importcn.hutool.core.date.DateUnit;importcn.hutool.core.date.DateUtil;publicclassAPP2{publicstaticvoidmain(String[]args){StringdateStr1="2023-03-01";//上......
  • 这可能是最全面的Java学习路线了
    大家好,我是大彬~我本科学的不是计算机,大四开始自学Java,并且拿到了几个互联网中大厂的offer。在学习Java这方面还是比较有经验的,下面我来分享下我整理的Java自学路线。在这里也提醒学弟学妹们,要尽早确定以后的方向,读研还是工作,找工作的话,也要尽快确定工作岗位,想转行的,需要花更多......
  • 【Java基础】Java8 使用 stream().filter()过滤List对象(查找符合条件的对象集合)
    本篇主要说明在Java8及以上版本中,使用stream().filter()来过滤List对象,查找符合条件的集合。一、集合对象定义集合对象以学生类(Student)为例,有学生的基本信息,包括:姓名,性别,年龄,身高,生日几项。我的学生类代码如下:packagecom.iot.productmanual.controller;importio.swagger.annota......
  • 【Java基础】map的遍历方式和map.forEach的使用
    Map的遍历方式常用的有两种,分为传统的map遍历方式和JDK1.8新的遍历方式,下面代码可以明显的看出其中的区别,话不多说,直接上代码,并执行结果,瞬间就能知道使用方式和对比结果了。importjava.util.HashMap;importjava.util.Map;/***<p>TestController此类用于:</p>*<p>@auth......