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

╰半橙微兮° 2023-07-07 00:44 16阅读 0赞

总结概括：

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;
        }
    
    }