首页 > 作文

Arrays.sort(arr)是什么排序及代码逻辑

更新时间:2023-04-04 21:26:01 阅读: 评论:0

在学习过程中观察到arrays.sort(arr)算法可以直接进行排序,但不清楚底层的代码逻辑是什么样子,记得自己之前在面试题里面也有面试官问这个问题,只能说研究之后发现还是比较复杂的,并不是网上说的快排或者二分插入之类的。

首先看源码:

 public static void sort(int[] a) {        dualpivotquicksort.sort(a, 0, a.length - 1, null, 0, 0);    }

它调用了dualpivotquicksort的sort方法,乍一看以为是快排,这是很多网上的博主的说法,继续点开向下看(代码太长,没耐心看可以直接跳过该段代码qwq):

 static void sort(int[] a, int left, int right,                     int[] work, int workba, int worklen) {        // u 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 quence).         */        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]);            } el 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;                }            } el { // 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,             * u quicksort instead of merge sort.             */            if (++count == max_run_count) {                sort(a, left, right, true);                return;            }        }        // check special cas        // implementation note: variable "right" is incread by 1.        if (run[count] == right++) { // the last run contains one element            run[++count] = right;        } el if (count == 1) { // the array is already sorted            return;        }        // determine alternation ba for merge        byte odd = 0;        for (int n = 1; (n <<= 1) < count; odd ^= 1);        // u or create temporary array b for merging        int[] b;                 // temp array; alternates with a        int ao, bo;              // array offts from 'left'        int blen = right - left; // space旧车置换 needed for b        if (work == null || worklen < blen || workba + blen > work.length) {            work = new int[blen];            workba = 0;        }        if (odd == 0) {            system.arraycopy(a, left, work, workba, blen);            b = a;            bo = 0;          贫困理由  a = work;            ao = workba - left;        } el {            b = work;            ao = 0;            bo = workba - 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];                    } el {                        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;        }    }

代码很长,简要翻译过来,这里分了好几种情况:

1.数组长度小于286

这里又会调用一个sort方法,点开该sort(),又会划分情况:

数组长度小于47,

当leftmost(导入的一个布尔参数)为true,则使用直接插入排序;

否则会调用另一种插入办法,这里可以观察到一个注释:

/*
* every element from adjoining part plays the role
* of ntinel, therefore this allows us to avoid the
* left range check on each iteration. moreover, we u
* the more optimized algorithm, so called pair inrtion
* sort, which is faster (in the context of quicksort)
* than traditional implementation of inrtion sort.
*/

大致意思是:相邻部分的每个元素都扮演着哨兵的角色,因此这允许我们避免在每次迭代中进行左范围检查。此外,我们使用了更优化的算法,即所谓的成对插入排序,它比插入排序的传统实现更快(在快速排序的上下文中)。

不过注意到,原函数参数传参在这里leftmost为true,所以一定是直接插入排序,以上作为了解。

数组长度大于47,采用一种快速排序的办法,这里因为代码太长,学艺不精,参考了一下:

至于大过inrtion_sort_threshold(47)的,用一种快速排序的方法:

1.从数列中挑出五个元素,称为 “基准”(pivot);

2.重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任差倍问题的公式一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;

3.递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

当数组长度大于286时

此时回到那段很长很长的代码段,在判断小于286的长度数组之后,从注解中:

// check if the array is nearly sorted

这里是指检查数组元素是不是快要排列好了,或者书面一点说,是不是有一定结构了,然后看后面的for循环,注意到一段代码:

 if (++count == max_run_count) {                sort(a, left, right, true);                return;            }

这里的sort和我们上面在数组长度小于286时的那个sort方法是同一个方法,而针对这个count,是用来记录逆序组的,打个比方:

此时有一个数组为1 5 6 9 8 7 2 3

当数组认定我们的顺序应该为升序时,从第一个数不畏浮云遮望眼的下一句开始数,此时9 8 7 2为降序,这就是逆序,将这四个数组合成一个组称为逆序组,然后再从3开始往后看。

当统计到一个逆序组时,count++,所以可以看出,count是用来记逆序组的,那么逆序组越多,这个结构就越混乱

max_run_count == 67 ,因此当count一直加到67时,就说明已经在一个混乱的临界值了,此时执行sort()方法

通过这一段分析,我们理一下思路:

​如果数组能运行到这里,说明数组的长度大于等于286。符合该条件时,我们要判断这个数组是否有一定的结构:

(1)count<67,说明不是那么混乱,有一定结构,跳过;

(2)count>=67,说明已经混乱了,没有结构,执行sort方法,而已知数组长度大于等于286,那么必然大于47,一定执行快速排序。

跳过之后,经过代码的一大堆前置操作,最后看见下面的代码里面一行注释:

//merging

显然,这里后面用到归并排序了,不详细赘述。

好了,最后总结:

数组长度小于286时,根据数组长度,分两种情况:数组长度小于47,使用直接插入排序数组长度大于47,使用快速排序数组长度大于286时,根据数组排序情况,分两种情况:数组内顺序较为混乱,即count逆序组数大于等于67,使用快速排序数组内有一定顺序,即count逆序组数小于67,使用归并排序

参考资料:

《java的arrays.sort()方法到底用的什么排序算法》htt农历月份的别称ps://www.cnblogs.com/baichunyu/p/11935995.html作者:白春雨

到此这篇关于arrays.sort(arr)是什么排序的文章就介绍到这了,更多相关arrays.sort(arr)排序内容请搜索www.887551.com以前的文章或继续浏览下面的相关文章希望大家以后多多支持www.887551.com!

本文发布于:2023-04-04 21:25:59,感谢您对本站的认可!

本文链接:https://www.wtabcd.cn/fanwen/zuowen/c3573221dfc9a71e9d46dfb0fb325499.html

版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

本文word下载地址:Arrays.sort(arr)是什么排序及代码逻辑.doc

本文 PDF 下载地址:Arrays.sort(arr)是什么排序及代码逻辑.pdf

标签:数组   逆序   长度   基准
相关文章
留言与评论(共有 0 条评论)
   
验证码:
Copyright ©2019-2022 Comsenz Inc.Powered by © 专利检索| 网站地图