java排列组合工具类 java字符串排列组合算法( 二 ) _生活百科

Timsort 的时间复杂度是 O(n log n)，与归并排序的时间复杂度相同，那它的优势是啥呢，实际上可以认为TimSort排序算法是归并排序算法的优化版，从它的三个特征就可以看出，第二个特征“混合的”，没错，它不单纯是一种算法，而是融合了归并算法和二分插入排序算法的精髓，因此能够在排序性能上表现优异。其它两个特征自适应和稳定性会在文章后面讲到。首先从算法性能统计上做个对比：

文章插图
可以看出TimSort排序算法，平均和最坏时间复杂度是O(nlogn)，最好时间复杂度是O(n)，空间复杂度是O(n)，且稳定的一种排序算法。在稳定算法中，从性能效果上对比来看和二叉排序算法一样。
3.1 TimSort的核心思想那TimSort算法的核心思想是什么呢，首先原始的TimSort对于长度小于64的数据（java中是32），会直接选择二分插入排序，效率很高。其次，TimSort算法的初衷认为现实中的数据总是部分有序的。这句话很关键，怎么理解呢，比如列表[5, 2, 8, 5, 7,23, 45, 63]，里面的[5, 2] 和 [8, 5] 和 [7, 23, 45,63] 各子列表中就是有序的，要么升序要么降序，这就是TimSort的基本根据。
基于此会发现待排序列表已经部分有序了，所以会在排序过程中尽量不要破坏这种顺序，就可以做到减少排序时间消耗。基本思想说完了，由此引出TimSort算法的几个概念：run和minrun 。
run是指连续升序或者连续降序的最长子序列（降序和升序可以相互转换），而minrun是一个设定值，实际上是每个run的长度最小值。所以TimSort会对待排序序列进行划分，找出连续有序的子序列，如果子序列长度不满足这点要求，就将后续数据插入到前面的子序列中。
举个例子，待排序序列[5, 2, 8, 5, 7,23, 45, 63]，如果minRun = 3，那分割后的run会有以下：[2, 5, 8]、[5,7,23,45,63] 两个子序列，最终通过合并这两个run得到[2,5,5,7,8,23,45,63]
是不是有个疑问： minrun怎么选择得到的？该值是通过大量的统计计算给出的minrun长度建议是在32 ~ 64之间取值效率比较高，具体在java代码中可能会有所不同。
接着来看，假设现在有序子序列已经拆分好了，需要进入到合并过程中了，TimSort是如何合并子序列的。对于归并排序我们都知道，序列先归后并，两两组合利用一个空数组直接进行比较就合并了。但是在TimSort算法中，合并过程是实时的，每次算出一个run就可能做一次合并。这个过程利用了栈结构，且需要遵循相邻的run才可以合并，也就是只有相邻的栈元素可以进行合并。
规则如下：假设当前有三个run子序列依次入栈，现在栈顶有三个元素从上至下依次为x3、x2、x1，它们的长度只要满足以下两个条件中的任何一个就进行合并：
（1）x1 <= x2 + x3
（2）x1 <= x2
满足这个条件的三个序列，像汉诺塔一样长度由下往上依次减小。刚才提到合并run的过程是实时的，也就是每产生一个run就进行一次合并操作。举例说明下，当前假设待排序序列[2,6,8,4,2,5,7,9,10,11,4,25,64,32,78,99]，其中再假设minrun=3是合理的。合并过程是这样的，注意这里的压栈和弹栈不一定需要对子序列本身进行操作，不是真的将子序列放入栈中，而只需要run标识以及长度即可，因为栈元素比较的是run长度。
（1）首先第一个run0是[2,6,8]，而第二个run1是[2,4,5]，此时依次将其放入栈中，发现满足第二个条件，这两个run进行合并，合并后将旧序列从栈中弹出，得到新的run0是[2,2,4,5,6,8]，再次压入栈中。
（2）继续从原序列中找到新的run1是[7,9,10,11]，压入栈中，此时run0和run1不满足条件不需要合并。继续从原序列中找到run2是[4,25,64]，压入栈中，此时满足第一个条件，这里的run1和run2需要进行合并，合并后将旧序列从栈中弹出，新run1是[4,7,9,10,11,25,64]，压入栈中。
（3）此时发现run0和run1满足第二个条件，继续合并弹出旧序列，得到新run0是[2,2,4,4,5,6,7,8,9,10,11,25,64]，压入栈中。
（4）继续从原序列中找到新的run1是[32,78,99]，压入栈中。此时发现没有更多元素，而条件是不满足的，依然进行一次合并，弹出旧序列，压入合并后的新子序列run0是[2,2,4,4,5,6,7,8,9,10,11,25,32,64,78,99]
（5）此时将run0拷贝到原序列就完成了排序

文章插图
为什么要设置这么两个合并run的严格条件，直接压栈合并岂不更好？目的是为了避免一个较长的有序片段和一个较小的有序片段进行归并，在合并长度上做到均衡效率才高。