算法—归并排序改良后亿级秒排及排序算法的极致

1.对小规模子数组使用插入排序

用不同的方法处理小规模问题能改进大多数递归算法的性能，因为递归会使小规模问题中方法的调用过于频繁，所以改进对它们的处理方法就能改进整个算法。对排序来说，我们已经知道插入排序（或者选择排序）非常简单，因此很可能在小数组上比归并排序更快。和之前一样，一幅可视轨迹图能够很好地说明归并排序的行为方式。图中的可视轨迹图显示的是改良后的归并排序的所有操作。使用插入排序处理小规模的子数组（比如长度小于15）一般可以将归并排序的运行时间缩短10%~15%。

2.测试数组是否已经有序

我们可以添加一个判断条件，如果a[mid]小于等于a[mid+1]，我们就认为数组已经是有序的并跳过merge()方法。这个改动不影响排序的递归调用，但是任意有序的子数组算法的运行时间就变为线性的了。

关键代码：

private final int CUTOFF = 7;private void sort(Comparable[] src, Comparable[] dst,                      int lo, int hi) {        // if (hi <= lo) return;        if (hi <= lo + CUTOFF) {            insertionSort(dst, lo, hi);            return;        }        int mid = lo + (hi - lo) / 2;        sort(dst, src, lo, mid);        sort(dst, src, mid+1, hi);         // if (!less(src[mid+1], src[mid])) {        //    for (int i = lo; i <= hi; i++) dst[i] = src[i];        //    return;        // }         // using System.arraycopy() is a bit faster than the above loop        if (!less(src[mid+1], src[mid])) {            System.arraycopy(src, lo, dst, lo, hi - lo + 1);            return;        }         merge(src, dst, lo, mid, hi);    }private void insertionSort(Comparable[] a, int lo,              int hi) {  for (int i = lo; i <= hi; i++)    for (int j = i; j > lo && less(a[j], a[j-1]); j--)      exch(a, j, j-1);}

海外公司注册、海外银行开户、跨境平台代入驻、VAT、EPR等知识和在线办理：https://www.xlkjsw.com

原标题：算法—归并排序改良后亿级秒排及排序算法的极致

关键词：排序