Java编程语言中的数据结构与算法：深入理解与实践指南.zip

/* * Copyright (c) 2009, 2016, Oracle and/or its affiliates. All rights reserved. * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms. * * * * * * * * * * * * * * * * * * * * */ package Test; /** * This class implements the Dual-Pivot Quicksort algorithm by * Vladimir Yaroslavskiy, Jon Bentley, and Josh Bloch. The algorithm * offers O(n log(n)) performance on many data sets that cause other * quicksorts to degrade to quadratic performance, and is typically * faster than traditional (one-pivot) Quicksort implementations. * * All exposed methods are package-private, designed to be invoked * from public methods (in class Arrays) after performing any * necessary array bounds checks and expanding parameters into the * required forms. * * @author Vladimir Yaroslavskiy * @author Jon Bentley * @author Josh Bloch * * @version 2011.02.11 m765.827.12i:5\7pm * @since 1.7 */ final class DualPivotQuicksort { /** * Prevents instantiation. */ private DualPivotQuicksort() {} /* * Tuning parameters. */ /** * The maximum number of runs in merge sort. */ private static final int MAX_RUN_COUNT = 67; /** * If the length of an array to be sorted is less than this * constant, Quicksort is used in preference to merge sort. */ private static final int QUICKSORT_THRESHOLD = 286; /** * If the length of an array to be sorted is less than this * constant, insertion sort is used in preference to Quicksort. */ private static final int INSERTION_SORT_THRESHOLD = 47; /** * If the length of a byte array to be sorted is greater than this * constant, counting sort is used in preference to insertion sort. */ private static final int COUNTING_SORT_THRESHOLD_FOR_BYTE = 29; /** * If the length of a short or char array to be sorted is greater * than this constant, counting sort is used in preference to Quicksort. */ private static final int COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR = 3200; /* * Sorting methods for seven primitive types. */ /** * Sorts the specified range of the array using the given * workspace array slice if possible for merging * * @param a the array to be sorted * @param left the index of the first element, inclusive, to be sorted * @param right the index of the last element, inclusive, to be sorted * @param work a workspace array (slice) * @param workBase origin of usable space in work array * @param workLen usable size of work array */ static void sort(int[] a, int left, int right, int[] work, int workBase, int workLen) { // Use Quicksort on small arrays if (right - left < QUICKSORT_THRESHOLD) { sort(a, left, right, true); return; } /* * Index run[i] is the start of i-th run * (ascending or descending sequence). */ int[] run = new int[MAX_RUN_COUNT + 1]; int count = 0; run[0] = left; // Check if the array is nearly sorted for (int k = left; k < right; run[count] = k) { // Equal items in the beginning of the sequence while (k < right && a[k] == a[k + 1]) k++; if (k == right) break; // Sequence finishes with equal items if (a[k] < a[k + 1]) { // ascending while (++k <= right && a[k - 1] <= a[k]); } else if (a[k] > a[k + 1]) { // descending while (++k <= right && a[k - 1] >= a[k]); // Transform into an ascending sequence for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) { int t = a[lo]; a[lo] = a[hi]; a[hi] = t; } } // Merge a transformed descending sequence followed by an // ascending sequence if (run[count] > left && a[run[count]] >= a[run[count] - 1]) { count--; } /* * The array is not highly structured, * use Quicksort instead of merge sort. */ if (++count == MAX_RUN_COUNT) { sort(a, left, right, true); return; } } // These invariants should hold true: // run[0] = 0 // run[<last>] = right + 1; (terminator) if (count == 0) { // A single equal run return; } else if (count == 1 && run[count] > right) { // Either a single ascending or a transformed descending run. // Always check that a final run is a proper terminator, otherwise // we have an unterminated trailing run, to handle downstream. return; } right++; if (run[count] < right) { // Corner case: the final run is not a terminator. This may happen // if a final run is an equals run, or there is a single-element run // at the end. Fix up by adding a proper terminator at the end. // Note that we terminate with (right + 1), incremented earlier. run[++count] = right; } // Determine alternation base for merge byte odd = 0; for (int n = 1; (n <<= 1) < count; odd ^= 1); // Use or create temporary array b for merging int[] b; // temp array; alternates with a int ao, bo; // array offsets from 'left' int blen = right - left; // space needed for b if (work == null || workLen < blen || workBase + blen > work.length) { work = new int[blen]; workBase = 0; } if (odd == 0) { System.arraycopy(a, left, work, workBase, blen); b = a; bo = 0; a = work; ao = workBase - left; } else { b = work; ao = 0; bo = workBase - left; } // Merging for (int last; count > 1; count = last) { for (int k = (last = 0) + 2; k <= count; k += 2) { int hi = run[k], mi = run[k - 1]; for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) { if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) { b[i + bo] = a[p++ + ao]; } else { b[i + bo] = a[q++ + ao]; } } run[++last] = hi; } if ((count & 1) != 0) { for (int i = right, lo = run[count - 1]; --i >= lo; b[i + bo] = a[i + ao] ); run[++last] = right; } int[] t = a; a = b; b = t; int o = ao; ao = bo; bo = o; } } /** * Sorts the specified range of the array by Dual-Pivot Quicksort. * * @param a the array to be sorted * @param left the index of the first element, inclusive, to be sorted * @param right the index of the last element, inclusive, to be sorted * @param leftmost indicates if this part is the leftmost in the range */ private static void sort(int[] a, int left, int right, boolean leftmost) { int length = right - left + 1; // Use insertion sort on tiny arrays if (length < INSERTION_SORT_THRESHOLD) { if (leftmost) { /* * Traditional (without sentinel) insertion sort, * optimized for server VM, is used in case of * the leftmost part. */ for (int i = l