Java的Arrays.sort()方法实例分析
导读:本文共2429.5字符,通常情况下阅读需要8分钟。同时您也可以点击右侧朗读,来听本文内容。按键盘←(左) →(右) 方向键可以翻页。
摘要: 首先看代码://UseQuicksortonsmallarraysif(right-left<QUICKSORT_THRESHOLD){//QUICKSORT_THRESHOLD=286sort(a,left,right,true);return;} 数组一进来,会碰到第一个阀值QUICKSORT_THRESHOLD(286),注解上说,小过... ...
目录
(为您整理了一些要点),点击可以直达。首先看代码:
//UseQuicksortonsmallarraysif(right-left<QUICKSORT_THRESHOLD){//QUICKSORT_THRESHOLD=286sort(a,left,right,true);return;}
数组一进来,会碰到第一个阀值QUICKSORT_THRESHOLD(286),注解上说,小过这个阀值的进入Quicksort (快速排序),其实并不全是,点进去sort(a, left, right, true);方法:
//Useinsertionsortontinyarraysif(length<INSERTION_SORT_THRESHOLD){if(leftmost){......
点进去后我们看到第二个阀值INSERTION_SORT_THRESHOLD(47),如果元素少于47这个阀值,就用插入排序,往下看确实如此:
/**Traditional(withoutsentinel)insertionsort,*optimizedforserverVM,isusedincaseof*theleftmostpart.*/for(inti=left,j=i;i<right;j=++i){intai=a[i+1];while(ai<a[j]){a[j+1]=a[j];if(j--==left){break;}}a[j+1]=ai;
元素少于47用插入排序
至于大过INSERTION_SORT_THRESHOLD(47)的,用一种快速排序的方法:
1.从数列中挑出五个元素,称为 “基准”(pivot);
2.重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;
3.递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
快速排序(Quick Sort)
这是少于阀值QUICKSORT_THRESHOLD(286)的两种情况,至于大于286的,它会进入归并排序(Merge Sort),但在此之前,它有个小动作:
//Checkifthearrayisnearlysortedfor(intk=left;k<right;run[count]=k){if(a[k]<a[k+1]){//ascendingwhile(++k<=right&&a[k-1]<=a[k]);}elseif(a[k]>a[k+1]){//descendingwhile(++k<=right&&a[k-1]>=a[k]);for(intlo=run[count]-1,hi=k;++lo<--hi;){intt=a[lo];a[lo]=a[hi];a[hi]=t;}}else{//equalfor(intm=MAX_RUN_LENGTH;++k<=right&&a[k-1]==a[k];){if(--m==0){sort(a,left,right,true);return;}}}/**Thearrayisnothighlystructured,*useQuicksortinsteadofmergesort.*/if(++count==MAX_RUN_COUNT){sort(a,left,right,true);return;}}
这里主要作用是看他数组具不具备结构:实际逻辑是分组排序,每降序为一个组,像1,9,8,7,6,8。9到6是降序,为一个组,然后把降序的一组排成升序:1,6,7,8,9,8。然后最后的8后面继续往后面找。
每遇到这样一个降序组,++count,当count大于MAX_RUN_COUNT(67),被判断为这个数组不具备结构(也就是这数据时而升时而降),然后送给之前的sort(里面的快速排序)的方法(The array is not highly structured,use Quicksort instead of merge sort.)
如果count少于MAX_RUN_COUNT(67)的,说明这个数组还有点结构,就继续往下走下面的归并排序。
总结:
从上面分析,Arrays.sort并不是单一的排序,而是插入排序,快速排序,归并排序三种排序的组合,为此我画了个流程图:
O(nlogn)只代表增长量级,同一个量级前面的常数也可以不一样,不同数量下面的实际运算时间也可以不一样。
数量非常小的情况下(就像上面说到的,少于47的),插入排序等可能会比快速排序更快。 所以数组少于47的会进入插入排序。
快排数据越无序越快(加入随机化后基本不会退化),平均常数最小,不需要额外空间,不稳定排序。
归排速度稳定,常数比快排略大,需要额外空间,稳定排序。
所以大于或等于47或少于286会进入快排,而在大于或等于286后,会有个小动作:“// Check if the array is nearly sorted”。这里第一个作用是先梳理一下数据方便后续的归并排序,第二个作用就是即便大于286,但在降序组太多的时候(被判断为没有结构的数据,The array is not highly structured,use Quicksort instead of merge sort.),要转回快速排序。
</div> <div class="zixun-tj-product adv-bottom"></div> </div> </div> <div class="prve-next-news">
Java的Arrays.sort()方法实例分析的详细内容,希望对您有所帮助,信息来源于网络。