基本数据结构

List

list排序实现：Arrays.sort().

DualPivotQuicksort 插入排序和双轴快排

_private _java.util.DualPivotQuicksort#sort(int[] a, int left, int right, boolean leftmost);
当小于47个时，使用插入排序。

插入排序

参数a为需要排序的数组，left代表需要排序的数组区间中最左边元素的索引，right代表区间中最右边元素的索引，leftmost代表该区间是否是数组中最左边的区间。
举个例子：
数组：[2, 4, 8, 5, 6, 3, 0, -3, 9]可以分成三个区间（2, 4, 8）{5, 6}<3, 0, -3, 9>
对于（）区间，left=0, right=2, leftmost=true
对于 {}区间， left=3, right=4, leftmost=false,同理可得<>区间的相应参数
当区间长度小于47时，该方法会采用插入排序；否则采用快速排序。

1、 当leftmost为true时，它会采用传统的插入排序（traditional insertion sort），代码也较简单，其过程类似打牌时抓牌插牌。
2、 当leftmost为false时，它采用一种新型的插入排序（pair insertion sort），改进之处在于每次遍历前面已排好序的数组需要 插入两个元素 ，而传统插入排序在遍历过程中只需要为一个元素找到合适的位置插入。对于插入排序来讲，其关键在于为待插入元素找到合适的插入位置，为了找到这个位置，需要遍历之前已经排好序的子数组，所以对于插入排序来讲，整个排序过程中其遍历的元素个数决定了它的性能。很显然， 每次遍历插入两个元素可以减少排序过程中遍历的元素个数 。
为左边区间时，pair insertion sort在左边元素比较大时，会越界。

双轴快排

TimSort 归并排序

• 大于286 归并或快排
  • 先使用TimSort的思想，找出正序或者倒序的数(run的栈)，然后合并各个run，最后完成TimSort
  • 找出的run个数大于67时，即认为它是一个比较乱序的数组，就直接采用双枢轴快速排序

对int数组的排序

Arrays.sort(int[] a);

• 小于47用插入排序
• 大于47用双轴快排 DualPivotQuicksort
• 大于286 归并或快排
  • 先使用TimSort的思想，找出正序或者倒序的数(run的栈)，然后合并各个run，最后完成TimSort
  • 找出的run个数大于67时，即认为它是一个比较乱序的数组，就直接采用双枢轴快速排序