在合并run的过程中会用到一种所谓的gallop(飞奔)模式,能够减少参与归并的数据长度,主要过程如下:假设有待归并的子序列x和y,如果x的前n个元素都是比y首元素小的,那这n个元素实际上就不用参与归并了 。原因就是这n个元素本来已经有序了,归并后还是在原来的位置 。同理而言,如果y的最后几个元素都比x最后一个元素小,那y的最后这n个元素也就不必参与归并操作了,这样就可以减少归并长度,减少来回复制多余数据的开销 。
3.2 Java源码探讨完TimSort的核心思想及其排序过程,现在来看下java代码是如何实现的 。Java1.8中的TimSort类位置在java.util.TimSort
staticvoid sort(T[] a, int lo, int hi, Comparator<? super T> c,T[] work, int workBase, int workLen) {assert c != null && a != null && lo >= 0 && lo <= hi && hi <= a.length;int nRemaining= hi - lo;if (nRemaining < 2)return;if (nRemaining < MIN_MERGE) {int initRunLen = countRunAndMakeAscending(a, lo, hi, c);binarySort(a, lo, hi, lo + initRunLen, c);return;}TimSort ts = new TimSort(a, c, work, workBase, workLen);int minRun = minRunLength(nRemaining);do {int runLen = countRunAndMakeAscending(a, lo, hi, c);if (runLen < minRun) {int force = nRemaining <= minRun ? nRemaining : minRun;binarySort(a, lo, lo + force, lo + runLen, c);runLen = force;}ts.pushRun(lo, runLen);ts.mergeCollapse();lo += runLen;nRemaining -= runLen;} while (nRemaining != 0);assert lo == hi;ts.mergeForceCollapse();assert ts.stackSize == 1;}变量nRemaining记录的是待排序列表中剩余元素个数,MIN_MERGE就是前文中提到的java中的minrun值是32 。如果nRemaining<32,用countRunAndMakeAscending(…)方法得到连续升序的最大个数,里面涉及到升序降序调整 。可以看到如果待排序列表小于32长度,就进行二分插入排序binarySort(…) 。
如果待排序列表长度大于32,调用TimSort对象的minRunLength(nRemaining) 计算minRun,这里就体现了动态自适应,具体来看代码中是如何做的 。r为取出长度n的二进制每次右移的一个溢出位值,n每次右移1位,直到长度n小于32 。n+r最终结果就是保留长度n的二进制的高5位再加上1个移除位 。根据注释可以看出:
- 如果待排序数组长度为2的n次幂,比如1024,则minRun = 32/2 = 16
- 其它情况的时候,逐位右移,直到找到介于16<=k<=32的值 。
private static int minRunLength(int n) {assert n >= 0;int r = 0;// Becomes 1 if any 1 bits are shifted offwhile (n >= MIN_MERGE) {r |= (n & 1);n >>= 1;}return n + r;}接下来在循环中进行处理:(1) 计算最小升序的run长度,如果小于minRun,使用二分插入排序将run的长度补充到minRun要求的长度 。
(2) ts.pushRun(lo, runLen) ,通过栈记录每个run的长度,这里lo是run的第一个元素的索引用来标记操作的是哪个run,runLen是run的长度 。
private void pushRun(int runBase, int runLen) {this.runBase[stackSize] = runBase;this.runLen[stackSize] = runLen;stackSize++;}(3)ts.mergeCollapse(); 通过计算前面提到的两个run合并的限定条件,分别是:- runLen[n-1] <= runLen[n] + runLen[n+1]
- runLen[n] <= runLen[n + 1]
private void mergeCollapse() {while (stackSize > 1) {int n = stackSize - 2;if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1]) {if (runLen[n - 1] < runLen[n + 1])n--;mergeAt(n);} else if (runLen[n] <= runLen[n + 1]) {mergeAt(n);} else {break; // Invariant is established}}}(4) 这里的mergeAt(n) 归并排序过程,之前有提到是经过优化后所谓gallop模式的归并排序,具体表现在方法中的gallopRight和gallopLeft方法 。int k = gallopRight(a[base2], a, base1, len1, 0, c);assert k >= 0;base1 += k;len1 -= k;if (len1 == 0)return;len2 = gallopLeft(a[base1 + len1 - 1], a, base2, len2, len2 - 1, c);assert len2 >= 0;if (len2 == 0)return;假设有X序列[4,9,21,23],Y序列[5,7,12,13,14,15,17],由于X中4小于Y序列最小元素5,所以合并后4必然是第一个元素;而Y序列中尾元素17比X中的[21,23]小,所以X中的[21,23]必然是合并最后两元素 。4. DivalQuickSort 算法介绍前文案例中提到SortedOps.java类,该类中对于基本类型的排序调用 Arrays.sort(ints); 或 Arrays.sort(longs); 再或 Arrays.sort(doubles); 使用了DivalQuickSort排序算法 。
public static void sort(int[] a) {DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);}4.1 DivalQuickSort 核心思想快速排序使用的是在排序序列中选择一个数作为分区点pivot,也就是所谓的轴,然后以此轴将数据分为左右两部分,大于该值的为一个区,小于该值的为一个区,利用分治和递归思想实现 。如下假设选择19为pivot值 。
- 免费姓氏头像logo在线制作工具 用自己的名字设计头像的软件
- ps切片工具怎么使用保存 使用切片选项设置
- 珍珠奶茶原材料和制作工具是怎样的
- ps钢笔工具绘制图形如何填颜色 Photoshop基础知识
- java中文乱码解决方法是什么 中文乱码的原因与解决方法
- 长视频录制哪个软件好 超好用的录屏工具
- 专业的网页制作工具有哪些 网页设计制作网站推荐
- 淘宝店铺采集软件哪个好 免费的电商数据采集工具
- 视频清晰度修复软件哪个好 10款视频增强画质工具
- iPad绘画工具有哪些 平板绘画软件推荐
