Java1.7之后Arrays.sort对数组排序DualPivotQuicksort.sort

喜欢ヅ旅行 2022-09-12 11:52 190阅读 0赞

有粉丝叫我帮他做一下这道题。。。。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAamF2YeadjumYs-WLhw_size_20_color_FFFFFF_t_70_g_se_x_16][]

额。。。。。。这同学应该好好听课啦 哈哈

int[] a = {25, 24, 12, 76, 101, 96, 28};
            Arrays.sort(a);//排序
            System.out.println("排序后数组如下");
            for (int i = 0; i < a.length; i++) {
                System.out.print(a[i] + " ,");
            }

既然写到这里了就看下底层实现吧

断点跟踪调用的是DualPivotQuicksort.java类的java双基准快速排序方法sort实现

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAamF2YeadjumYs-WLhw_size_20_color_FFFFFF_t_70_g_se_x_16 1][]

跟踪进去就是具体排序方法的实现、其中具体方法：参数 int\[\] a是需被排序的int数组, left和right是该数组中需要被排序的部分的左右界限. 而后面的work, workBase和workLen三个参数其实并不会参与双基准快速排序, 而是当系统认为本数组更适合使用归并排序(merge sort)的时候, 供归并排序使用。具体代码算法源码如下。

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) {
                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]);
                    for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
                        int t = a[lo]; a[lo] = a[hi]; a[hi] = t;
                    }
                } else { // equal
                    for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
                        if (--m == 0) {
                            sort(a, left, right, true);
                            return;
                        }
                    }
                }
    
                /*
                 * The array is not highly structured,
                 * use Quicksort instead of merge sort.
                 */
                if (++count == MAX_RUN_COUNT) {
                    sort(a, left, right, true);
                    return;
                }
            }
    
            // Check special cases
            // Implementation note: variable "right" is increased by 1.
            if (run[count] == right++) { // The last run contains one element
                run[++count] = right;
            } else if (count == 1) { // The array is already sorted
                return;
            }
    
            // 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;
            }
        }

虽然看似简单的一行代码其实底层的实现也是很复杂的、对算法感兴趣的同学可以仔细看看底层实现。

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAamF2YeadjumYs-WLhw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/fb5338f656bf4b9180b06697ba69a175.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAamF2YeadjumYs-WLhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/f8f74176680a4bc494d052054c4aa215.png