yyy48,吴亚军背景,杭州甲醛检测
简介
mergesort对已经反向排好序的输入时复杂度为o(n^2)，而timsort就是针对这种情况，对mergesort进行优化而产生的，平均复杂度为n*o(log n),最好的情况为o(n)，最坏情况n*o(log n)。并且timsort是一种稳定性排序。思想是先对待排序列进行分区，然后再对分区进行合并，看起来和mergesort步骤一样，但是其中有一些针对反向和大规模数据的优化处理。
归并排序的优化思想
归并排序有以下几点优化方法：
和快速排序一样，对于小数组可以使用插入排序或者选择排序，避免递归调用。
在merge()调用之前，可以判断一下a[mid]是否小于等于a[mid+1]。如果是的话那么就不用归并了，数组已经是有序的。原因很简单，既然两个子数组已经有序了，那么a[mid]是第一个子数组的最大值，a[mid+1]是第二个子数组的最小值。当a[mid]<=a[mid+1]时，数组整体有序。
为了节省将元素复制到辅助数组作用的时间，可以在递归调用的每个层次交换原始数组与辅助数组的角色。
在merge()方法中的归并过程需要判断i和j是否已经越界，即某半边已经用尽。可以用另一种方式，去掉检测是否某半边已经用尽的代码。具体步骤是将数组a[]的后半部分以降序的方式复制到aux[]，然后从两端归并。对于数组{1,2,3}和{2,3,5},第一个子数组照常复制，第二个则从后往前复制，最终aux[]中的元素为{1,2,3,5,3,2}。这种方法的缺点是使得归并排序变为不稳定排序。代码实现如下：
我要评论
void merge(int[] a, int lo, int mid, int hi, int[] aux) {
for (int k = lo; k <= mid; k++) {
aux[k] = a[k];
}
for (int k = mid + 1;k <= hi; k++) {
aux[k] = a[hi - k + mid + 1];
}
int i = lo, j = hi; //从两端往中间
for (int k = lo; k <= hi; k++)
if (aux[i] <= aux[j]) a[k] = aux[i++];
else a[k] = aux[j--];
}
timsort的步骤
分区
分区的思想是扫描一次数组，把连续正序列（如果是升序排序，那么正序列就是升序序列），或者【严格】（保证排序算法的稳定性）的反序列做为一个分区（run），如果是反序列，把分区里的元素反转一下。 例如
1，2，3，6，4，5，8，6，4 划分分区结果为
[1,2,3,6],[4,5,8],[6,4]
然后反转反序列
[1,2,3,6],[4,5,8],[4,6]
合并
考虑一个极端的例子，比如分区的长度分别为 10000，10，1000，10，10，我们当然希望是先让10个10合并成20， 20和1000合并成1020如此下去， 如果从从左往右顺序合并的话，每次都用到10000这个数组和去小的数组合并，代价太大了。所以我们可以用一个策略来优化合并的顺序。
实例
以java中的comparabletimsort.sort()为例子， 用了一个run stack来确定是否应该合并，
if (nremaining < min_merge) {
int initrunlen = countrunandmakeascending(a, lo, hi);
binarysort(a, lo, hi, lo + initrunlen);
return;
}
小于min_merge（32）的排序，分区后直接用二分插入排序
int minrun = minrunlength(nremaining);
do {
//找出下一个分区的起始位置，同时也对反向序列做了翻转处理
int runlen = countrunandmakeascending(a, lo, hi);
//保证run stack中的run的都大于minrun ，如果当前分区太小，就从后面取出元素补足
if (runlen < minrun) {
int force = nremaining <= minrun ? nremaining : minrun;
binarysort(a, lo, lo + force, lo + runlen);
runlen = force;
}
//把run放入 run stack中
ts.pushrun(lo, runlen);
//判断是否应该合并，i是从栈顶开始的，知道不能合并为止
//1. runlen[i - 3] > runlen[i - 2] + runlen[i - 1]
//2. runlen[i - 2] > runlen[i - 1]
ts.mergecollapse();
lo += runlen;
nremaining -= runlen;
} while (nremaining != 0);
// merge all remaining runs to complete sort
assert lo == hi;
//合并剩下的run
ts.mergeforcecollapse();
assert ts.stacksize == 1;
在看里面的一个比较重要的函数
/**
* 如果后2个run的长度加起来比前面一个长，则使用中间位置的run和前后长度更短的run一个合并
* 如果后2个run的长度加起来比前面一个短，则把后面2个run合并
*/
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
}
}
}
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
浅析我对 String、StringBuilder、StringBuffer 的理解
使用IDEA搭建SSM框架的详细教程(spring + springMVC +MyBatis)
Springboot整合freemarker 404问题解决方案
引入mybatis-plus报 Invalid bound statement错误问题的解决方法
网友评论