数组中排序

  1.  public static void main(String[] args) {
  2.         int[] nums = {1,3,5,2,7,6,9};
  4.         Arrays.sort(nums);
  5.         System.out.println("增序排列");
  6.         for (int i = 0; i < nums.length; i++) {
  7.             System.out.println("nums:" + i + " :" + nums[i]);
  8.         }
  10.         //要实现减序排序，得通过包装类型数组，基本类型数组是不行的
  11.         Integer[] integers = new Integer[]{2,555,3,789,4,1,543};
  12.         System.out.println("减序排列");
  13.         //通过一个比较器，比较函数可以通过比较进而
  15.         Arrays.sort(integers, new Comparator<Integer>() {
  16.             @Override
  17.             public int compare(Integer o1, Integer o2) {
  18.                 return o2 - o1;
  19.             }
  20.         });
  22.         System.out.println("部分增序排列");
  23.         for (int i = 0; i < nums.length; i++) {
  24.             System.out.println("integers:" + i + " :" + integers[i]);
  25.         }
  27.         int[] ints = {1222,77,5,3,444,76,7};
  28.         // 对数组的[2,5)位进行排序
  29.         Arrays.sort(ints,2,5);
  30.         for (int i = 0; i < ints.length; i++) {
  31.             System.out.println("ints:" + i + " :" + ints[i]);
  32.         }
  33.     }

比较函数

一个比较函数，它对某些对象集合进行总排序。比较器可以传递给排序方法（例如Collections.sort或Arrays.sort ）以允许精确控制排序顺序。

  1. package java.util;
  4. public class Arrays {
  5.     // 排序
  6.      public static void sort(int[] a) {
  7.         DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
  8.     }
  10.     // 部分排序
  11.     public static void sort(int[] a, int fromIndex, int toIndex) {
  12.         rangeCheck(a.length, fromIndex, toIndex);
  13.         DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
  14.     }
  15. }

DualPivotQuicksort 双轴快速排序

  1. /**
  2.      * Sorts the specified range of the array using the given
  3.      * workspace array slice if possible for merging
  4.      *
  5.      * @param a the array to be sorted
  6.      * @param left the index of the first element, inclusive, to be sorted
  7.      * @param right the index of the last element, inclusive, to be sorted
  8.      * @param work a workspace array (slice)
  9.      * @param workBase origin of usable space in work array
  10.      * @param workLen usable size of work array
  11.      */
  13. /**
  14.     *使用给定的
  15.     *工作区数组切片（如果可能）用于合并
  16.     *@param a要排序的数组
  17.     *@param将第一个元素的索引（包括）留作排序
  18.     *@param right要排序的最后一个元素（包括）的索引
  19.     *@param工作空间数组（切片）
  20.     *@param workBase工作阵列中可用空间的来源
  21.     *@param worken工作数组的可用大小
  22.     */ 
  24.     static void sort(int[] a, int left, int right,
  25.                      int[] work, int workBase, int workLen) {
  26.         // Use Quicksort on small arrays
  27.         if (right - left < QUICKSORT_THRESHOLD) {
  28.             sort(a, left, right, true);
  29.             return;
  30.         }
  32.         /*
  33.          * Index run[i] is the start of i-th run
  34.          * (ascending or descending sequence).
  35.          */
  36.         int[] run = new int[MAX_RUN_COUNT + 1];
  37.         int count = 0; run[0] = left;
  39.         // Check if the array is nearly sorted
  40.         for (int k = left; k < right; run[count] = k) {
  41.             if (a[k] < a[k + 1]) { // ascending
  42.                 while (++k <= right && a[k - 1] <= a[k]);
  43.             } else if (a[k] > a[k + 1]) { // descending
  44.                 while (++k <= right && a[k - 1] >= a[k]);
  45.                 for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
  46.                     int t = a[lo]; a[lo] = a[hi]; a[hi] = t;
  47.                 }
  48.             } else { // equal
  49.                 for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
  50.                     if (--m == 0) {
  51.                         sort(a, left, right, true);
  52.                         return;
  53.                     }
  54.                 }
  55.             }
  57.             /*
  58.              * The array is not highly structured,
  59.              * use Quicksort instead of merge sort.
  60.              */
  61.             if (++count == MAX_RUN_COUNT) {
  62.                 sort(a, left, right, true);
  63.                 return;
  64.             }
  65.         }
  67.         // Check special cases
  68.         // Implementation note: variable "right" is increased by 1.
  69.         if (run[count] == right++) { // The last run contains one element
  70.             run[++count] = right;
  71.         } else if (count == 1) { // The array is already sorted
  72.             return;
  73.         }
  75.         // Determine alternation base for merge
  76.         byte odd = 0;
  77.         for (int n = 1; (n <<= 1) < count; odd ^= 1);
  79.         // Use or create temporary array b for merging
  80.         int[] b;                 // temp array; alternates with a
  81.         int ao, bo;              // array offsets from 'left'
  82.         int blen = right - left; // space needed for b
  83.         if (work == null || workLen < blen || workBase + blen > work.length) {
  84.             work = new int[blen];
  85.             workBase = 0;
  86.         }
  87.         if (odd == 0) {
  88.             System.arraycopy(a, left, work, workBase, blen);
  89.             b = a;
  90.             bo = 0;
  91.             a = work;
  92.             ao = workBase - left;
  93.         } else {
  94.             b = work;
  95.             ao = 0;
  96.             bo = workBase - left;
  97.         }
  99.         // Merging
  100.         for (int last; count > 1; count = last) {
  101.             for (int k = (last = 0) + 2; k <= count; k += 2) {
  102.                 int hi = run[k], mi = run[k - 1];
  103.                 for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
  104.                     if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) {
  105.                         b[i + bo] = a[p++ + ao];
  106.                     } else {
  107.                         b[i + bo] = a[q++ + ao];
  108.                     }
  109.                 }
  110.                 run[++last] = hi;
  111.             }
  112.             if ((count & 1) != 0) {
  113.                 for (int i = right, lo = run[count - 1]; --i >= lo;
  114.                     b[i + bo] = a[i + ao]
  115.                 );
  116.                 run[++last] = right;
  117.             }
  118.             int[] t = a; a = b; b = t;
  119.             int o = ao; ao = bo; bo = o;
  120.         }
  121.     }

https://blog.csdn.net/github_38838414/article/details/80642329

注意：博客中的非27，根据源码为47