本文主要是介绍如何对一个亿的数组进行快速排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
总结概括：
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;}}
这篇关于如何对一个亿的数组进行快速排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
