企业做网站公司有哪些,汕头市通信建设管理办公室网站,济南高端定制网站建设,深圳网站品牌建设TimSort算法是一种起源于归并排序和插入排序的混合排序算法#xff0c;设计初衷是为了在真实世界中的各种数据中能够有较好的性能。该算法最初是由Tim Peters于2002年在Python语言中提出的。 TimSort 是一个归并排序做了大量优化的版本号。对归并排序排在已经反向排好序的输入… TimSort算法是一种起源于归并排序和插入排序的混合排序算法设计初衷是为了在真实世界中的各种数据中能够有较好的性能。该算法最初是由Tim Peters于2002年在Python语言中提出的。 TimSort 是一个归并排序做了大量优化的版本号。对归并排序排在已经反向排好序的输入时表现O(n2)的特点做了特别优化。对已经正向排好序的输入降低回溯。对两种情况混合一会升序。一会降序的输入处理比較好。 在jdk1.7之后。Arrays类中的sort方法有一个分支推断当LegacyMergeSort.userRequested为true的情况下採用legacyMergeSort否则採用ComparableTimSort。而且在legacyMergeSort的凝视上标明了该方法会在以后的jdk版本号中废弃因此以后Arrays类中的sort方法将採用ComparableTimSort类中的sort方法。 span stylefont-family:Microsoft YaHei;public static void sort(Object[] a, int fromIndex, int toIndex) {if (LegacyMergeSort.userRequested)legacyMergeSort(a, fromIndex, toIndex);elseComparableTimSort.sort(a, fromIndex, toIndex);
} /span以下是ComparableTimSort的sort方法span stylefont-family:Microsoft YaHei;static void sort(Object[] a) {sort(a, 0, a.length);
}static void sort(Object[] a, int lo, int hi) {rangeCheck(a.length, lo, hi);int nRemaining hi - lo;if (nRemaining 2)return; // Arrays of size 0 and 1 are always sorted// If array is small, do a mini-TimSort with no mergesif (nRemaining MIN_MERGE) {int initRunLen countRunAndMakeAscending(a, lo, hi);binarySort(a, lo, hi, lo initRunLen);return;}/*** March over the array once, left to right, finding natural runs,* extending short natural runs to minRun elements, and merging runs* to maintain stack invariant.*/ComparableTimSort ts new ComparableTimSort(a);int minRun minRunLength(nRemaining);do {// Identify next runint runLen countRunAndMakeAscending(a, lo, hi);// If run is short, extend to min(minRun, nRemaining)if (runLen minRun) {int force nRemaining minRun ? nRemaining : minRun;binarySort(a, lo, lo force, lo runLen);runLen force;}// Push run onto pending-run stack, and maybe mergets.pushRun(lo, runLen);ts.mergeCollapse();// Advance to find next runlo runLen;nRemaining - runLen;} while (nRemaining ! 0);// Merge all remaining runs to complete sortassert lo hi;ts.mergeForceCollapse();assert ts.stackSize 1;
}/span1传入的待排序数组若小于阈值MIN_MERGEJava实现中为32。Python实现中为64。则调用 binarySort这是一个不包括合并操作的 mini-TimSort。 a) 从数组開始处找到一组连接升序或严格降序找到后翻转的数 b) Binary Sort使用二分查找的方法将兴许的数插入之前的已排序数组。binarySort 对数组 a[lo:hi] 进行排序而且a[lo:start] 是已经排好序的。算法的思路是对a[start:hi] 中的元素。每次使用binarySearch 为它在 a[lo:start] 中找到对应位置并插入。 2開始真正的TimSort过程 2.1 选取minRun大小之后待排序数组将被分成以minRun大小为区块的一块块子数组 a) 假设数组大小为2的N次幂则返回16MIN_MERGE / 2 b) 其它情况下逐位向右位移即除以2直到找到介于16和32间的一个数 minRun span stylefont-family:Microsoft YaHei;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;}/span这个函数依据 n 计算出相应的 natural run 的最小长度。MIN_MERGE 默觉得32假设n小于此值那么返回n 本身。否则会将 n 不断地右移。直到少于 MIN_MERGE同一时候记录一个 r 值r 代表最后一次移位n时。n最低位是0还是1。 最后返回 n r这也意味着仅仅保留最高的 5 位。再加上第六位。 2.2do-while 2.2.1找到初始的一组升序数列countRunAndMakeAscending 会找到一个run 。这个run 必须是已经排序的。而且函数会保证它为升序也就是说假设找到的是一个降序的。会对其进行翻转。 2.2.2若这组区块大小小于minRun则将兴许的数补足利用binarySort 对 run 进行扩展。而且扩展后run 仍然是有序的。 2.2.3当前的 run 位于 a[lo:runLen] 将其入栈ts.pushRun(lo, runLen);//为兴许merge各区块作准备记录当前已排序的各区块的大小 2.2.4对当前的各区块进行mergemerge会满足下面原则如果XYZ为相邻的三个区块 a) 仅仅对相邻的区块merge b) 若当前区块数仅为2If XY。将X和Y merge b) 若当前区块数3If XYZ。将X和Y merge。直到同一时候满足XYZ和YZ 因为要合并的两个 run 是已经排序的所以合并的时候有会特别的技巧。如果两个 run 是 run1,run2 先用 gallopRight在 run1 里使用 binarySearch 查找run2 首元素 的位置k, 那么 run1 中 k 前面的元素就是合并后最小的那些元素。然后在run2 中查找run1 尾元素 的位置 len2 那么run2 中 len2 后面的那些元素就是合并后最大的那些元素。最后依据len1 与len2 大小。调用mergeLo 或者 mergeHi 将剩余元素合并。 2.2.5 反复2.2.1 ~ 2.2.4直到将待排序数组排序完 2.2.6 Final Merge假设此时还有区块未merge则合并它们 3演示样例 *注意*为了演示方便我将TimSort中的minRun直接设置为2否则我不能用非常小的数组演示。。。同一时候把MIN_MERGE也改成2默觉得32这样避免直接进入binary sort。 初始数组为[7,5,1,2,6,8,10,12,4,3,9,11,13,15,16,14] 寻找连续的降序或升序序列 (2.2.1)。同一时候countRunAndMakeAscending 函数会保证它为升序 [1,5,7] [2,6,8,10,12,4,3,9,11,13,15,16,14] 入栈 (2.2.3) 当前的栈区块为[3] 进入merge循环 (2.2.4) do not merge由于栈大小仅为1 寻找连续的降序或升序序列 (2.2.1) [1,5,7] [2,6,8,10,12] [4,3,9,11,13,15,16,14] 入栈 (2.2.3) 当前的栈区块为[3, 5] 进入merge循环 (2.2.4) merge由于runLen[0]runLen[1] 1) gallopRight寻找run1的第一个元素应当插入run0中哪个位置”2”应当插入”1”之后然后就能够忽略之前run0的元素都比run1的第一个元素小 2) gallopLeft寻找run0的最后一个元素应当插入run1中哪个位置”7”应当插入”8”之前然后就能够忽略之后run1的元素都比run0的最后一个元素大这样须要排序的元素就仅剩下[5,7] [2,6]然后进行mergeLow 完毕之后的结果 [1,2,5,6,7,8,10,12] [4,3,9,11,13,15,16,14] 入栈 (2.2.3) 当前的栈区块为[8] 退出当前merge循环由于栈中的区块仅为1 寻找连续的降序或升序序列 (2.2.1) [1,2,5,6,7,8,10,12] [3,4] [9,11,13,15,16,14] 入栈 (2.2.3) 当前的栈区块大小为[8,2] 进入merge循环 (2.2.4) do not merge由于runLen[0]runLen[1] 寻找连续的降序或升序序列 (2.2.1) [1,2,5,6,7,8,10,12] [3,4] [9,11,13,15,16] [14] 入栈 (2.2.3) 当前的栈区块为[8,2,5] do not merege run1与run2由于不满足runLen[0]runLen[1]runLen[2] merge run2与run3由于runLen[1]runLen[2] 1) gallopRight发现run1和run2就已经排好序 完毕之后的结果 [1,2,5,6,7,8,10,12] [3,4,9,11,13,15,16] [14] 入栈 (2.2.3) 当前入栈的区块大小为[8,7] 退出merge循环由于runLen[0]runLen[1] 寻找连续的降序或升序序列 (2.2.1) 最后仅仅剩下[14]这个元素[1,2,5,6,7,8,10,12] [3,4,9,11,13,15,16] [14] 入栈 (2.2.3) 当前入栈的区块大小为[8,7,1] 进入merge循环 (2.2.4) merge由于runLen[0]runLen[1]runLen[2] 由于runLen[0]runLen[2]所以将run1和run2先合并。否则将run0和run1先合并 1) gallopRight 2) gallopLeft 这样须要排序的元素剩下[13,15] [14]然后进行mergeHigh 完毕之后的结果 [1,2,5,6,7,8,10,12] [3,4,9,11,13,14,15,16] 当前入栈的区块为[8,8] 继续merge由于runLen[0]runLen[1] 1) gallopRight 2) gallopLeft 须要排序的元素剩下[5,6,7,8,10,12] [3,4,9,11]。然后进行mergeHigh 完毕之后的结果 [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16] 当前入栈的区块大小为[16] 不须要final merge由于当前栈大小为1 结束 參考 http://www.lifebackup.cn/timsort-java7.html http://blog.csdn.net/on_1y/article/details/30109975 http://en.wikipedia.org/wiki/Timsort 转载于:https://www.cnblogs.com/lxjshuju/p/7081959.html
