快速排序改进优化

2024-09-02 11:48
文章标签 优化 快速 排序 改进

本文主要是介绍快速排序改进优化,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

以前写的快速排序,基本上按下面伪代码这个套路写出来就完了,但其实对于快排,可以通过很多方面来进行改进以达到更好的效率。

algorithm quicksort(A, lo, hi) isif lo < hi thenp := partition(A, lo, hi)quicksort(A, lo, p)quicksort(A, p + 1, hi)algorithm partition(A, lo, hi) ispivot := A[lo]i := lo - 1j := hi + 1loop foreverdoi := i + 1while A[i] < pivotdoj := j - 1while A[j] > pivotif i >= j thenreturn jswap A[i] with A[j]

快排模拟
先回顾一下上面快排的模拟图
分析:

  • 首先,清楚快排原理的同志都知道,快排特别热衷于凌乱的数据,最好情况下时间复杂度能达到O(nlogn),空间复杂度为O(logn);但是对于基本有序或者倒序的数据则无能为力,时间复杂度直接降到O(n^2),空间复杂度为O( n ) 。对于这种情况,取一个合理的基准值就很重要了。
    一种较为稳妥的方法是随机选取数组中的某个位置,而不是总是顽固地选择最右端的元素,这样确实可以避免排序的退化。
    再回想我们为什么要取随机值?就是为了避免输入数据有序造成的异常,如果一种方法能够在这种情况下利用这种原有的有序性岂不是更好吗?三值取中法就是这样的方法,它的选取方法是先从数组的开头、结尾和中间选取3个元素,再取这3个元素的中间值作为划分的基准。首先,三值取中法本身带有一定的随机性,所以能够很好的处理随机数据;其次,它使得最坏情况几乎不可能发生,如果数组原本就具有有序性,那么按照原始的划分方法,取到的3个元素中必然有2个将被划分到大于(或小于)v的值所在的数组中,而三值取中法则扭转了这种不利;最后,与随机化方法相比,三值取中法省去了生成随机数的开销。
  • 其次,在快速排序算法的递归实现中,存在一种不太好的现象:随着递归层层深入,大量数据被分割成了小数组;快排对于大数组的划分可以迅速地将元素移动到它正确位置的附近,比如说对1024进行一次均等划分,那么某个元素可能会移动数百个单位位置,若进行4次均等划分,元素在正确位置上的概率就从1/1024骤升到1/64,考虑到64与1024的绝对数值,这是相当高的效率;然而对于小数组,快速排序的效率就不那么理想了,对于16个元素的数组,快速排序也要划分4次才能把它移动到正确的位置上,相对于之前几百个位置的移动,小数组排序一次只能移动几个单位的位置。
    换句话说,快速排序对少量数据的划分远不如它对大量数据的划分这么划算,当排序进入到小数组阶段后,它将多次因为这些小数组而频繁调用自身,但获得的收益并不大,我姑且把这种现象叫做小数组的边际效益。采取分治递归策略的排序算法(如归并排序)都存在同样的问题,所以这类排序都可以在这方面优化。对大量数据排序时,我们应该在前期利用快速排序的特点,让这些数据迅速移动到正确位置附近,然后在后期消除小数组的边际效应。
    消除边际效应的一个方法就是设定一个M值,当数组元素个数小于M时,视为小数组,此时快速排序就直接返回,最后把数组处理得差不多时,再用其它排序方法对数组进行最终排序。那么M值应该取多少?又应该选择何种排序算法进行最终排序?
    首先回答第二个问题,因为它的答案是显而易见的。对接近有序的数据排序,没有什么算法比插入排序更合适了,插入排序的执行开销与所有元素偏离自己正确位置的距离成正比。

最后看一下结合上面两种改进方法写出来的快排:

package sort;public class QuickSortDemo2 {private static void print(long[] a) {System.out.print("a : ");for (int i = 0; i < a.length; i++) {System.out.print(a[i] + " ");}System.out.println();}private static void quickSort(long[] a, int left, int right) {
//      if(right<=left){
//          return;
//      }//当数组长度比较短并且基本有序时,使用插入排序会有比较好的效率提升if (right - left + 1 <= 10) {insertSort(a, left, right);} else {//取left和right的中间值,有两个好处:1、防止对于基本有序的数组进行多余无效的交换;2、能够很巧妙的为数组越界作参考标准long median = getMedian(a, left, right);int partition = partitionInt(a, left, right, median);quickSort(a, left, partition-1);quickSort(a, partition+1, right);}}private static int partitionInt(long[] a, int left, int right, long median) {int leftPtr = left;int rightPtr = right - 1;while (true) {while (a[++leftPtr] < median)   //因为median取的是left、right和center的中间值,所以仅通过一句判断很巧妙的实现了数组越界的判断;while (a[--rightPtr] > median)  //同上;if(leftPtr >= rightPtr){break;}swap(a,leftPtr,rightPtr);}swap(a, leftPtr, right-1);return leftPtr;}private static long getMedian(long[] a, int left, int right) {int center = (left + right) / 2;if (a[left] > a[center]) {swap(a, left, center);}if (a[left] > a[right]) {swap(a, left, right);}if (a[center] > a[right]) {swap(a, center, right);}swap(a, center, right - 1); //将中值放到right-1位置,后面的比较替换只针对left+1~right-2return a[right - 1];}private static void insertSort(long[] a, int left, int right) {int in, out;for (out = left + 1; out <= right; out++) {in = out;long temp = a[out];while (in > left && a[in - 1] > temp) {a[in] = a[in - 1];--in;}a[in] = temp;}}private static void swap(long[] a, int i, int j) {long temp = a[i];a[i] = a[j];a[j] = temp;}public static void main(String[] args) {long[] a = new long[10000];for (int i = 0; i < a.length; i++) {a[i] = (long) (Math.random() * 99);}print(a);long startTime = System.currentTimeMillis();quickSort(a, 0, a.length - 1);long endTime = System.currentTimeMillis();System.out.println("use: " + (endTime - startTime) + "ms");print(a);}}

github:
https://github.com/aweneves/Algorithm1/blob/master/src/sort/QuickSortDemo2.java

这篇关于快速排序改进优化的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1129869

相关文章

MyBatisPlus如何优化千万级数据的CRUD

《MyBatisPlus如何优化千万级数据的CRUD》最近负责的一个项目,数据库表量级破千万,每次执行CRUD都像走钢丝,稍有不慎就引起数据库报警,本文就结合这个项目的实战经验,聊聊MyBatisPl... 目录背景一、MyBATis Plus 简介二、千万级数据的挑战三、优化 CRUD 的关键策略1. 查

一文详解Java Stream的sorted自定义排序

《一文详解JavaStream的sorted自定义排序》Javastream中的sorted方法是用于对流中的元素进行排序的方法,它可以接受一个comparator参数,用于指定排序规则,sorte... 目录一、sorted 操作的基础原理二、自定义排序的实现方式1. Comparator 接口的 Lam

Linux如何快速检查服务器的硬件配置和性能指标

《Linux如何快速检查服务器的硬件配置和性能指标》在运维和开发工作中,我们经常需要快速检查Linux服务器的硬件配置和性能指标,本文将以CentOS为例,介绍如何通过命令行快速获取这些关键信息,... 目录引言一、查询CPU核心数编程(几C?)1. 使用 nproc(最简单)2. 使用 lscpu(详细信

一文详解如何在idea中快速搭建一个Spring Boot项目

《一文详解如何在idea中快速搭建一个SpringBoot项目》IntelliJIDEA作为Java开发者的‌首选IDE‌,深度集成SpringBoot支持,可一键生成项目骨架、智能配置依赖,这篇文... 目录前言1、创建项目名称2、勾选需要的依赖3、在setting中检查maven4、编写数据源5、开启热

MybatisX快速生成增删改查的方法示例

《MybatisX快速生成增删改查的方法示例》MybatisX是基于IDEA的MyBatis/MyBatis-Plus开发插件,本文主要介绍了MybatisX快速生成增删改查的方法示例,文中通过示例代... 目录1 安装2 基本功能2.1 XML跳转2.2 代码生成2.2.1 生成.xml中的sql语句头2

8种快速易用的Python Matplotlib数据可视化方法汇总(附源码)

《8种快速易用的PythonMatplotlib数据可视化方法汇总(附源码)》你是否曾经面对一堆复杂的数据,却不知道如何让它们变得直观易懂?别慌,Python的Matplotlib库是你数据可视化的... 目录引言1. 折线图(Line Plot)——趋势分析2. 柱状图(Bar Chart)——对比分析3

一文教你Java如何快速构建项目骨架

《一文教你Java如何快速构建项目骨架》在Java项目开发过程中,构建项目骨架是一项繁琐但又基础重要的工作,Java领域有许多代码生成工具可以帮助我们快速完成这一任务,下面就跟随小编一起来了解下... 目录一、代码生成工具概述常用 Java 代码生成工具简介代码生成工具的优势二、使用 MyBATis Gen

Java List排序实例代码详解

《JavaList排序实例代码详解》:本文主要介绍JavaList排序的相关资料,Java排序方法包括自然排序、自定义排序、Lambda简化及多条件排序,实现灵活且代码简洁,文中通过代码介绍的... 目录一、自然排序二、自定义排序规则三、使用 Lambda 表达式简化 Comparator四、多条件排序五、

JAVA数组中五种常见排序方法整理汇总

《JAVA数组中五种常见排序方法整理汇总》本文给大家分享五种常用的Java数组排序方法整理,每种方法结合示例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录前言:法一:Arrays.sort()法二:冒泡排序法三:选择排序法四:反转排序法五:直接插入排序前言:几种常用的Java数组排序

SpringBoot中HTTP连接池的配置与优化

《SpringBoot中HTTP连接池的配置与优化》这篇文章主要为大家详细介绍了SpringBoot中HTTP连接池的配置与优化的相关知识,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一... 目录一、HTTP连接池的核心价值二、Spring Boot集成方案方案1:Apache HttpCl