如何对一个亿的数组进行快速排序

2023-11-08 20:38

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

总结概括:  

      1.数据结构   归并排序 (也是后续排序 LRD)

       2.多线程     ForkJoin框架  繁重任务的并行计算框架,map-reduce思想

计算代码

/****@author dongsheng*@date 2019/1/18 22:58*@Description:*@version 1.0.0*/
public class ArrayMergerSortTask extends RecursiveAction {// implementation details follow:static final int THRESHOLD = 1000;final int[] array;final int lo, hi;ArrayMergerSortTask(int[] array, int lo, int hi) {this.array = array;this.lo = lo;this.hi = hi;}ArrayMergerSortTask(int[] array) {this(array, 0, array.length);}protected void compute() {if (hi - lo < THRESHOLD)		//小于1000,就排序sortSequentially(lo, hi);else {int mid = (lo + hi) >>> 1;		//大于1000,拆分invokeAll(new ArrayMergerSortTask(array, lo, mid),new ArrayMergerSortTask(array, mid, hi));merge(lo, mid, hi);}}void sortSequentially(int lo, int hi) {Arrays.sort(array, lo, hi);		//利用JDK自带的排序进行}void merge(int lo, int mid, int hi) {int[] buf = Arrays.copyOfRange(array, lo, mid);for (int i = 0, j = lo, k = mid; i < buf.length; j++)array[j] = (k == hi || buf[i] < array[k]) ? buf[i++] : array[k++];}public static void main(String[] args) throws Exception {// 这里以一个长度为2千的数组做示例int length = 2_000;int[] array = new int[length];// 填充数值Random random = new Random();for (int i = 0; i < length; i++) {array[i] = random.nextInt();System.out.println(array[i]);}// 利用forkjoinpool来完成多线程快速归并排序ArrayMergerSortTask stask = new ArrayMergerSortTask(array);ForkJoinPool pool = new ForkJoinPool();pool.submit(stask);// 等待任务完成stask.get();System.out.println("----------排序后的结果:");for (int d : array) {System.out.println(d);}}
}

RecursiveAction  
    ForkJoinTask 的子类, 是 ForkJoinTask 的一个子类,它代表了一类最简单的 ForkJoinTask:不需要返回值,当子任务都执行完毕之后,不需要进行中间结果的组合。如果我们从 RecursiveAction 开始继承,那么我们只需要重载 protected void compute() 方法。

源码代码

/******* Written by Doug Lea with assistance from members of JCP JSR-166* Expert Group and released to the public domain, as explained at* http://creativecommons.org/publicdomain/zero/1.0/*/package java.util.concurrent;/*** A recursive resultless {@link ForkJoinTask}.  This class* establishes conventions to parameterize resultless actions as* {@code Void} {@code ForkJoinTask}s. Because {@code null} is the* only valid value of type {@code Void}, methods such as {@code join}* always return {@code null} upon completion.** <p><b>Sample Usages.</b> Here is a simple but complete ForkJoin* sort that sorts a given {@code long[]} array:**  <pre> {@code* static class SortTask extends RecursiveAction {*   final long[] array; final int lo, hi;*   SortTask(long[] array, int lo, int hi) {*     this.array = array; this.lo = lo; this.hi = hi;*   }*   SortTask(long[] array) { this(array, 0, array.length); }*   protected void compute() {*     if (hi - lo < THRESHOLD)*       sortSequentially(lo, hi);*     else {*       int mid = (lo + hi) >>> 1;*       invokeAll(new SortTask(array, lo, mid),*                 new SortTask(array, mid, hi));*       merge(lo, mid, hi);*     }*   }*   // implementation details follow:*   static final int THRESHOLD = 1000;*   void sortSequentially(int lo, int hi) {*     Arrays.sort(array, lo, hi);*   }*   void merge(int lo, int mid, int hi) {*     long[] buf = Arrays.copyOfRange(array, lo, mid);*     for (int i = 0, j = lo, k = mid; i < buf.length; j++)*       array[j] = (k == hi || buf[i] < array[k]) ?*         buf[i++] : array[k++];*   }* }}</pre>** You could then sort {@code anArray} by creating {@code new* SortTask(anArray)} and invoking it in a ForkJoinPool.  As a more* concrete simple example, the following task increments each element* of an array:*  <pre> {@code* class IncrementTask extends RecursiveAction {*   final long[] array; final int lo, hi;*   IncrementTask(long[] array, int lo, int hi) {*     this.array = array; this.lo = lo; this.hi = hi;*   }*   protected void compute() {*     if (hi - lo < THRESHOLD) {*       for (int i = lo; i < hi; ++i)*         array[i]++;*     }*     else {*       int mid = (lo + hi) >>> 1;*       invokeAll(new IncrementTask(array, lo, mid),*                 new IncrementTask(array, mid, hi));*     }*   }* }}</pre>** <p>The following example illustrates some refinements and idioms* that may lead to better performance: RecursiveActions need not be* fully recursive, so long as they maintain the basic* divide-and-conquer approach. Here is a class that sums the squares* of each element of a double array, by subdividing out only the* right-hand-sides of repeated divisions by two, and keeping track of* them with a chain of {@code next} references. It uses a dynamic* threshold based on method {@code getSurplusQueuedTaskCount}, but* counterbalances potential excess partitioning by directly* performing leaf actions on unstolen tasks rather than further* subdividing.**  <pre> {@code* double sumOfSquares(ForkJoinPool pool, double[] array) {*   int n = array.length;*   Applyer a = new Applyer(array, 0, n, null);*   pool.invoke(a);*   return a.result;* }** class Applyer extends RecursiveAction {*   final double[] array;*   final int lo, hi;*   double result;*   Applyer next; // keeps track of right-hand-side tasks*   Applyer(double[] array, int lo, int hi, Applyer next) {*     this.array = array; this.lo = lo; this.hi = hi;*     this.next = next;*   }**   double atLeaf(int l, int h) {*     double sum = 0;*     for (int i = l; i < h; ++i) // perform leftmost base step*       sum += array[i] * array[i];*     return sum;*   }**   protected void compute() {*     int l = lo;*     int h = hi;*     Applyer right = null;*     while (h - l > 1 && getSurplusQueuedTaskCount() <= 3) {*       int mid = (l + h) >>> 1;*       right = new Applyer(array, mid, h, right);*       right.fork();*       h = mid;*     }*     double sum = atLeaf(l, h);*     while (right != null) {*       if (right.tryUnfork()) // directly calculate if not stolen*         sum += right.atLeaf(right.lo, right.hi);*       else {*         right.join();*         sum += right.result;*       }*       right = right.next;*     }*     result = sum;*   }* }}</pre>** @since 1.7* @author Doug Lea*/
public abstract class RecursiveAction extends ForkJoinTask<Void> {private static final long serialVersionUID = 5232453952276485070L;/*** The main computation performed by this task.*/protected abstract void compute();/*** Always returns {@code null}.** @return {@code null} always*/public final Void getRawResult() { return null; }/*** Requires null completion value.*/protected final void setRawResult(Void mustBeNull) { }/*** Implements execution conventions for RecursiveActions.*/protected final boolean exec() {compute();return true;}}

 

这篇关于如何对一个亿的数组进行快速排序的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

如何使用Lombok进行spring 注入

《如何使用Lombok进行spring注入》本文介绍如何用Lombok简化Spring注入,推荐优先使用setter注入,通过注解自动生成getter/setter及构造器,减少冗余代码,提升开发效... Lombok为了开发环境简化代码,好处不用多说。spring 注入方式为2种,构造器注入和setter

MySQL进行数据库审计的详细步骤和示例代码

《MySQL进行数据库审计的详细步骤和示例代码》数据库审计通过触发器、内置功能及第三方工具记录和监控数据库活动,确保安全、完整与合规,Java代码实现自动化日志记录,整合分析系统提升监控效率,本文给大... 目录一、数据库审计的基本概念二、使用触发器进行数据库审计1. 创建审计表2. 创建触发器三、Java

MySQL深分页进行性能优化的常见方法

《MySQL深分页进行性能优化的常见方法》在Web应用中,分页查询是数据库操作中的常见需求,然而,在面对大型数据集时,深分页(deeppagination)却成为了性能优化的一个挑战,在本文中,我们将... 目录引言:深分页,真的只是“翻页慢”那么简单吗?一、背景介绍二、深分页的性能问题三、业务场景分析四、

SpringBoot结合Docker进行容器化处理指南

《SpringBoot结合Docker进行容器化处理指南》在当今快速发展的软件工程领域,SpringBoot和Docker已经成为现代Java开发者的必备工具,本文将深入讲解如何将一个SpringBo... 目录前言一、为什么选择 Spring Bootjavascript + docker1. 快速部署与

linux解压缩 xxx.jar文件进行内部操作过程

《linux解压缩xxx.jar文件进行内部操作过程》:本文主要介绍linux解压缩xxx.jar文件进行内部操作,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、解压文件二、压缩文件总结一、解压文件1、把 xxx.jar 文件放在服务器上,并进入当前目录#

SpringBoot中如何使用Assert进行断言校验

《SpringBoot中如何使用Assert进行断言校验》Java提供了内置的assert机制,而Spring框架也提供了更强大的Assert工具类来帮助开发者进行参数校验和状态检查,下... 目录前言一、Java 原生assert简介1.1 使用方式1.2 示例代码1.3 优缺点分析二、Spring Fr

Java中的数组与集合基本用法详解

《Java中的数组与集合基本用法详解》本文介绍了Java数组和集合框架的基础知识,数组部分涵盖了一维、二维及多维数组的声明、初始化、访问与遍历方法,以及Arrays类的常用操作,对Java数组与集合相... 目录一、Java数组基础1.1 数组结构概述1.2 一维数组1.2.1 声明与初始化1.2.2 访问

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案(推荐)2. 模糊匹配方案参数化查询示例使用场景建议性能优

关于集合与数组转换实现方法

《关于集合与数组转换实现方法》:本文主要介绍关于集合与数组转换实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、Arrays.asList()1.1、方法作用1.2、内部实现1.3、修改元素的影响1.4、注意事项2、list.toArray()2.1、方

Golang如何对cron进行二次封装实现指定时间执行定时任务

《Golang如何对cron进行二次封装实现指定时间执行定时任务》:本文主要介绍Golang如何对cron进行二次封装实现指定时间执行定时任务问题,具有很好的参考价值,希望对大家有所帮助,如有错误... 目录背景cron库下载代码示例【1】结构体定义【2】定时任务开启【3】使用示例【4】控制台输出总结背景