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

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

快速排序

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

  • 基础快排:在序列本身有序的情况下复杂度为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附近的元素交换位置即可。

  1. 那么当全部都排序完毕时,也就是鼠标指的那个点处,i 和 Rt 重合时,退出循环
  1. 因为按顺序应该是 小于V ,V,==V,>V ,所以只要将V和 <V 处的最后一个元素交换位置即可

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

实现一下吧:文章来源地址https://www.toymoban.com/news/detail-458362.html

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 = l + random.nextInt(r + 1 - l);      //生成一个不超过数组长度的随机数
        swap(arr, randomInt, l);                                 //把他和首元素交换位置

        //定义需要的变量
        int Lt = l;             //放在数组最左边
        int Rt = r + 1;         //到时候先-1再交换
        int i = l + 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);
            }
        }
        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;
    }

    public static void main(String[] args) {
        Integer[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 10, 9};
        Quick.quicksort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");		//1,2,3,4,5,6,7,8,9,10
        }
    }
}

到了这里,关于三路快排Java版(带思路分析)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【排序算法】 快速排序(快排)!图解+实现详解!

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

    2024年02月05日
    浏览(39)
  • 数据结构——三路划分(快排优化)

    刷Leetcode时遇到的问题,用普通的快排去跑,发现有问题。  普通的Hoare或者其他的快排好像都没有直接解决掉这个问题,当一个数重复出现的时候,用普通的快排效率其实并没有那么高。所以,这也是普通快排的缺点之一。 所以,在一个元素重复出现多次的时候,可以用三

    2024年02月08日
    浏览(50)
  • leetcodeT912-快排优化-三路划分

    因为快排的名声太大 并且快排在某些场景下比较慢,所以leetcode\\\"修理\\\"了一下快排 特意设计了一些专门针对快排的测试用例 所以用快排过不了这一题 我们遇到了第一个为难快排的测试用例全是重复值2 我们发现快排在遇到全是重复值的数据时, 这里以左右指针法为例 每次右指

    2024年02月08日
    浏览(52)
  • 八大排序算法之快速排序(下篇)(快排的优化+非递归快排的实现)

    目录 一.前言 1.快速排序的实现: 快速排序的单趟排序(排升序)(快慢指针法实现):​ 2.未经优化的快排的缺陷 二.快速排序的优化 1.三数取中优化 优化思路: 2. 小区间插入排序优化 小区间插排优化的递归快排: 三.非递归快速排序的实现 1.快排一个难以避免的缺陷(暂不考虑三指针

    2024年02月02日
    浏览(50)
  • 快速排序(快排) (C语言实现)

    👋我是Brant_zero,一名学习C/C++的在读大学生。 🌏️我的博客主页​​​​​​➡➡Brant_zero的主页 🙏🙏 欢迎大家的关注,你们的关注是我创作的最大动力 🙏🙏         本篇博客学习内容是快速排序,快速排序有多种不同的版本和优化,我们这次的目的就是将这些版本

    2023年04月09日
    浏览(34)
  • 三路排序算法(Java 实例代码)

    目录   三路排序算法 一、概念及其介绍 二、适用说明 四、Java 实例代码 QuickSort3Ways.java 文件代码:   一、概念及其介绍 三路快速排序是双路快速排序的进一步改进版本,三路排序算法把排序的数据分为三部分,分别为小于 v,等于 v,大于 v,v 为标定值,这样三部分的数据

    2024年02月10日
    浏览(60)
  • 八大排序算法之快速排序(上篇)(未经优化的快排)

    目录 一.关于快速排序的总体算法思想 1.冒泡排序(交换排序) (以排升序为例) 2.快速排序的总体思想简介(以排升序为例)  二.快速排序单趟排序的算法接口设计(以排升序为例) 单趟排序实现的方法一:hoare版本(左右指针法) 代码实现:  单趟排序实现的方法二:挖坑法  代码实现

    2023年04月08日
    浏览(40)
  • 【面试准备 算法题】用快排的思路对单链表进行排序(不能进行值拷贝)

    最近面试碰到这个题目感觉很有意思,既考察二分/递归的思想,也考察链表的操作,尤其对于边界情况的处理需要细心 给定单链表进行排序(链表节点定义如上) 不能通过值拷贝来实现元素交换(必须通过修改next指针实现 元素位置排序 )

    2024年02月13日
    浏览(37)
  • 图解快排——快速排序算法(quick sort)

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

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

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

    2024年02月05日
    浏览(54)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包