Arrays.Sort()中的那些排序算法

语言: CN / TW / HK

本文基于JDK 1.8.0_211撰写,基于java.util.Arrays.sort()方法浅谈目前Java所用到的排序算法,仅个人见解和笔记,若有问题欢迎指证,着重介绍其中的插入排序以及TimSort排序,其源于Python,并于JDK1.7引入Java以替代原有的归并排序。

本文基于JDK 1.8.0_211撰写,基于java.util.Arrays.sort()方法浅谈目前Java所用到的排序算法,仅个人见解和笔记,若有问题欢迎指证,着重介绍其中的TimSort排序,其源于Python,并于JDK1.7引入Java以替代原有的归并排序。

引入

Arrays.Sort方法所用的排序算法主要涉及以下三种:双轴快速排序(DualPivotQuicksort)、归并排序(MergeSort)、TimSort,也同时包含了一些非基于比较的排序算法:例如计数排序。其具体最终使用哪一种排序算法通常根据类型以及输入长度来动态抉择

  • 输入数组类型为基础类型时,采用双轴快速排序,辅以计数排序;
public static void sort(int[] a) { DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);}

  • 输入数组类型为包装类型时,采用归并排序或TimSort(除非经过特殊的配置,否则默认采用TimSort)
public static void sort(Object[] a) { if (LegacyMergeSort.userRequested)  legacyMergeSort(a); else ComparableTimSort.sort(a, 0, a.length, null, 0, 0);} public static <T> void sort(T[] a, Comparator<? super T> c) { if (c == null) {  sort(a); } else {  if (LegacyMergeSort.userRequested)   legacyMergeSort(a, c); else  TimSort.sort(a, 0, a.length, c, null, 0, 0); }} /** To be removed in a future release. */ private static <T> void legacyMergeSort(T[] a, Comparator<? super T> c) { T[] aux = a.clone(); if (c==null)  mergeSort(aux, a, 0, a.length, 0); else mergeSort(aux, a, 0, a.length, 0, c); }

排序稳定性

假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i] = r[j],且 r[i] 在 r[j] 之前,而在排序后的序列中,r[i] 仍在 r[j] 之前,则称这种排序算法是稳定的;否则称为不稳定的。

稳定性的含义:如果我们需要在二次排序后保持原有排序的意义,就需要使用到稳定性的算法

例子:我们要对一组商品排序,商品存在两个属性:价格和销量。当我们按照价格从高到低排序后,要再按照销量对其排序,这时,如果要保证销量相同的商品仍保持价格从高到低的顺序,就必须使用稳定性算法。

快速排序与双轴快速排序

快速排序简介

单轴快速排序 即为我们最常见的一种快速排序方式,我们选取一个基准值(pivot),将待排序数组划分为两部分:大于pivot 和 小于pivot,再对这两部分进行单轴快速排序... 但是这种方式对于输入数组中有很多重复元素时效率不太理想。

单轴三取样切分快速排序 作为单轴快速排序的优化版本,其主要优化相同元素过多情况下的快排效率,同样选取一个基准值,但将待排序数组划分三部分: 大于pivot、等于pivot、大于pivot。

双轴快速排序 选取两个 基准值pivot1,pivot2,且保证pivot1<=pivot2,其具体实现与三取样切分类似,不过时将待排序数组划分以下三部分:小于pivot,介于pivot1与pivot2之间,大于pivot2。

DualPivotQuicksort实现优化

Java在实现DualPivotQuickSort时,并未盲目使用双轴快速排序,而是基于输入长度选取排序算法

(1)针对int、long、float、double四种类型,跟据长度选取的排序算法如下:

  • 当待排序数目小于47,采用插入排序
  • 当待排序数目小于286,采用双轴快排
  • 当待排序数目大于286,采用归并排序

我们暂且将其称之为一个标准的双轴快排

static void sort(int[] a, int left, int right,      int[] work, int workBase, int workLen) {  // Use Quicksort on small arrays  if (right - left < QUICKSORT_THRESHOLD) {   sort(a, left, right, true);   return;  }  // Use MergingSort  doMerge(); }private static void sort(int[] a, int left, int right, boolean leftmost) {  // Use insertion sort on tiny arrays  if (length < INSERTION_SORT_THRESHOLD) {   doInertionSort();  }  doDualPivotQuickSort();}

 

(2)针对short、char两种类型,根据长度选取的排序算法如下:

  • 当待排序数目小于3200,采用标准双轴快排
  • 当待排序数目大于3200,采用计数排序(CountingSort)

(3)针对byte类型,根据长度选取的排序算法如下:

  • 当待排序数目小于29,采用插入排序
  • 当待排序数目大于29,采用计数排序(CountingSort)

非基于比较排序算法-计数排序

计数排序与传统的基于比较的排序算法不同,其不通过比较来排序。我们常见的非基于比较的排序算法有三种:桶排序、计数排序(特殊桶排序)、基数排序,有兴趣的可以逐个去了解,这里主要讲解计数排序。

使用前提

使用计数排序待排序内容需要是一个有界的序列,且可用整数表示

引入

计数排序顾名思义即需要统计数组中的元素个数,通过另外一个数组的地址表示输入元素的值,数组的值表示元素个数。最后再将这个数组反向输出即可完成排序,见下方示例:

假设:一组范围在 0~10 之间的数字,9, 3, 5, 4, 9, 1, 2, 7, 8,1,3, 6, 5, 3, 4, 0, 10, 9, 7, 9

第一步:建立一个数组来统计每个元素出现的个数,因为是0~10,则建立如下数组 Count

 

 

 

第二步:遍历输入数组,将获取到的内容放置到Count 数组对应的位置,使当前位置+1,例如当前为9:

以此类推,遍历完整个输入数组,则得到一个完整状态的Count:

这时候,Count中记录了输入数组所有的元素出现的次数,将Count数组按次数输出即可得到最终排序输出:

0, 1, 1, 2, 3, 3, 3, 4, 4, 5, 5, 6, 7, 7, 8, 9, 9, 9, 9, 10

计数排序的稳定性与最终实现

根据上面稳定性的定义,大家不难发现上面的实现过程不能保证基数排序的稳定性,而实际上计数排序是一个稳定的排序算法,下面我们通过上面那个例子来引出计数排序的最终实现。

例子:输入数组  [ 0,9,5,4,5 ],范围0 ~ 9

第一步:将Count数组中所记录的内容进行更改,由记录当前元素的出现的次数 修正为  记录当前索引出现的次数和当前索引之前所有元素次数的和,这样在索引中存储的值就是其真实的排序后排位数,例如9的值为5,则9的排序后的位置就是第5位:

第二步:我们从后向前遍历原序列,此时为5,则在最终排序序列的位置为4(索引为3)的地方放置5,并将Count序列的5索引处的值-1。

以此类推:到第二个5时,Count数组中的值为3(索引为2),这样就保证了插入排序的稳定性。

 

 

源码实现

 

/** The number of distinct byte values. */private static final int NUM_BYTE_VALUES = 1 << 8;static void sort(byte[] a, int left, int right) { int[] count = new int[NUM_BYTE_VALUES];  // 建立count数组 for (int i = left - 1; ++i <= right;  count[a[i] - Byte.MIN_VALUE]++ ); // 从尾部开始遍历 for (int i = NUM_BYTE_VALUES, k = right + 1; k > left; ) {
while (count[--i] == 0); byte value = (byte) (i + Byte.MIN_VALUE); int s = count[i]; do { a[--k] = value; } while (--s > 0); } }

TimSort

Timsort是工业级算法,其混用插入排序与归并排序,二分搜索等算法,亮点是充分利用待排序数据可能部分有序的事实,并且依据待排序数据内容动态改变排序策略——选择性进行归并以及galloping。另外TimSort是一个稳定的算法,其最好的执行情况要优于普通归并排序,最坏情况与归并排序相仿:

针对小数据优化

针对输入长度较短的数组排序,很多轻量级排序即可胜任,故TimSort在基于输入数组长度的条件下,做出如下优化:

当输入序列的长度小于基准值时,将采用插入排序直接对输入序列排序。基准值的选取:(1)Python:64(2)Java:32

此外上面提到的插入排序,Java的实现中,对这部分做了优化,严格来说这里使用的是二分插入排序。将插入排序与二分查找进行了结合。因为插入排序的索引左侧均是有序序列

  • 传统意义上需要单个依次向前比较,直到找到新插入元素放置的位置;
  • 二分插入排序,则在此处采用二分查找来确认插入元素的放置位置。

TimSort简要流程

TimSort is a hybrid sorting algorithm that uses insertion sort and merge sort.

The algorithm reorders the input array from left to right by finding consecutive (disjoint) sorted segments (called “runs” from hereon). If the run is too short, it is extended using insertion sort.  The lengths of the generated runs are added to an array named runLen. Whenever a new run is added to runLen, a method named mergeCollapse merges runs until the last 3 elements in runLen satisfy the following two conditions (the “invariant”):

  1. runLen [n-2] > runLen [n-1] + runLen [n]
  2. runLen [n-1] > runLen [n] 

Here n is the index of the last run in runLen.  The intention is that checking this invariant on the top 3 runs in runLen in fact guarantees that all runs satisfy it. At the very end, all runs are merged, yielding a sorted version of the input array.

TimSort算法通过找到连续的(不相交)排序的段(此后称为“Run”),如果Run过短,则使用插入排序扩充。生成的Run的长度被称添加到一个名为runLen数组中,每当将新Run添加到runLen时,名为mergeCollapse的方法就会尝试合并Run,直到runLen中的元素元素满足两个恒定的不等式。到最后,所有Run都将合并成一个Run,从而生成输入数组的排序版本。

基本概念 - Run

TimSort算法中,将有序子序列(升序序列严格降序序列)称之为Run,例如如下将排序序列:1,2,3,4,5,4,3,6,8,10

则上面的序列所有的Run如下:1,2,3,4,5,5,3,2,2,6,8,10

TimSort中会区分其序列为升序还是降序,如果是降序会强行反转Run,使其成为升序,则上述的序列经过反转后即为:1,2,3,4,5,5,2,3,2,6,8,10

注意:Run必须是升序(可以相等)和严格降序(不能相等),严格降序的原因是保证TimSort稳定性,因为降序需要反转

基本概念 - MinRun

当两个数组归并时,当这个数组Run的数目等于或略小于2的乘方时,效率最高(基本数学概念参考:listsort.txt)。

反过来说,我们需要得到一个Run的最小长度使得其划分的Run的数目达到上述标准准,即:选取32-64(16-32)这个范围作为MinRun的范围,使得原排序数组可以被MinRun分割成N份,这个N等于或略小于2的乘方

  • 如果当前的Run长度小于MinRun:尝试把后面的元素通过插入排序放入Run中,以尽量达到MinRun的长度(剩余长度满足的情况下);
  • 如果当前的Run长度大于MinRun:不处理。

通过上述的操作我们就收获了一系列Run,将其放置到堆栈runLen中,并尝试对其进行归并:

 

/**     * A stack of pending runs yet to be merged. Run i starts at     * address base[i] and extends for len[i] elements. It's always     * true (so long as the indices are in bounds) that:     *     * runBase[i] + runLen[i] == runBase[i + 1]     *     * so we could cut the storage for this, but it's a minor amount,     * and keeping all the info explicit simplifies the code.     */    private int stackSize = 0; // Number of pending runs on stack    private final int[] runBase;    private final int[] runLen;  /*   * 初始化部分截取   * 分配runs-to-be-merged堆栈(不能扩大)   */ int stackLen = (len < 120 ? 5 : len < 1542 ? 10 : len < 119151 ? 24 : 49); runBase = new int[stackLen]; runLen = new int[stackLen]; /**   * Pushes the specified run onto the pending-run stack.   *   * @param runBase index of the first element in the&n.........
分享到: