Collections.sort in JDK6:MergeSort

       本文是对JDK6中Collections.sort方法的源码解析,也可以看作是对Comparison method violates its general contract!的后续分析。在JDK6中,该方法底层使用的是经过优化后的归并排序,废话不多说,直接看源码。

public static <T> void sort(List<T> list, Comparator<? super T> c) {
	Object[] a = list.toArray();
	Arrays.sort(a, (Comparator)c);
	ListIterator i = list.listIterator();
	for (int j=0; j<a.length; j++) {
	    i.next();
	    i.set(a[j]);
	}
}

       将list转成数组,然后调用Arrays.sort方法排序,最后将排好顺序的值覆盖到原list上。

public static <T> void sort(T[] a, Comparator<? super T> c) {
	T[] aux = (T[])a.clone();
	if (c==null)
		mergeSort(aux, a, 0, a.length, 0);
	else
		mergeSort(aux, a, 0, a.length, 0, c);
}

       克隆一个数组,如果比较器为空,mergeSort(aux, a, 0, a.length, 0);如果比较器不为空,mergeSort(aux, a, 0, a.length, 0, c);二者内部算法实现一致,只是比较元素的方法不一样。下面来看归并排序的实现,看其是如何优化的。

private static void mergeSort(Object[] src,
				  Object[] dest,
				  int low, int high, int off,
				  Comparator c) {
	int length = high - low;

	// Insertion sort on smallest arrays
	if (length < INSERTIONSORT_THRESHOLD) {
	    for (int i=low; i<high; i++)
			for (int j=i; j>low && c.compare(dest[j-1], dest[j])>0; j--)
				swap(dest, j, j-1);
	    return;
	}

	// Recursively sort halves of dest into src
	int destLow  = low;
	int destHigh = high;
	low  += off;
	high += off;
	int mid = (low + high) >>> 1;
	mergeSort(dest, src, low, mid, -off, c);
	mergeSort(dest, src, mid, high, -off, c);

	// If list is already sorted, just copy from src to dest.  This is an
	// optimization that results in faster sorts for nearly ordered lists.
	if (c.compare(src[mid-1], src[mid]) <= 0) {
	   System.arraycopy(src, low, dest, destLow, length);
	   return;
	}

	// Merge sorted halves (now in src) into dest
	for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
		if (q >= high || p < mid && c.compare(src[p], src[q]) <= 0)
			dest[i] = src[p++];
		else
			dest[i] = src[q++];
	}
}

       我们分段来看。

int length = high - low;

// Insertion sort on smallest arrays
if (length < INSERTIONSORT_THRESHOLD) {
	for (int i=low; i<high; i++)
		for (int j=i; j>low && c.compare(dest[j-1], dest[j])>0; j--)
			swap(dest, j, j-1);
	return;
}

       这里有一个常量INSERTIONSORT_THRESHOLD。

/**
 * Tuning parameter: list size at or below which insertion sort will be
 * used in preference to mergesort or quicksort.
 */
private static final int INSERTIONSORT_THRESHOLD = 7;

       当数组长度<7时,这里使用了直接插入排序。直接插入排序的过程可以看这个视频,插入排序适用于小数列的排序。这里是JDK6中归并排序的第一个优化

// Recursively sort halves of dest into src
int destLow  = low;
int destHigh = high;
low  += off;
high += off;
int mid = (low + high) >>> 1;// 中间索引,相当于(low + high) / 2
mergeSort(dest, src, low, mid, -off, c);// 排序左边
mergeSort(dest, src, mid, high, -off, c);// 排序右边

       这里开始递归排序,我们不需要关注off变量,这个变量是排序数组中部分区域的时候使用的,而我们要排序的是整个数组。

// If list is already sorted, just copy from src to dest.  This is an
// optimization that results in faster sorts for nearly ordered lists.
if (c.compare(src[mid-1], src[mid]) <= 0) {
   System.arraycopy(src, low, dest, destLow, length);
   return;
}

       左边和右边排好序之后,开始合并。这时src[low ~ mid - 1]和src[mid ~ high - 1]都是有序的,这时比较src[mid - 1]和src[mid],如果前者比后者小,那么皆大欢喜,真个src数组就是有序的了,只需将其复制到目标数组后,就完成了排序,不过这种碰运气的几率会比较小。这里是JDK6中归并排序的第二个优化

// Merge sorted halves (now in src) into dest
for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
	if (q >= high || p < mid && c.compare(src[p], src[q]) <= 0)
		dest[i] = src[p++];
	else
		dest[i] = src[q++];
}

       程序执行到这里,进行传统的合并操作。其过程如下图:

       初始状态:

       循环一次后:

       每次都比较src[p]和src[q],将较小的元素存储到dest[i],不断的循环比较,直至整个数组都有序。

       最终:

      JDK6中的排序是基于传统的归并排序做了部分优化,这两个优化都很简单,实际上效率并未提高多少。所以在JDK7中将其替换为TimSort,下回分解。

      (完)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏有趣的Python

2-玩转数据结构-不要小瞧数组

数组中索引从0开始,Java语法中要求数组存放同一类型的元素,可以通过中括号下标的方式取到元素。

5294
来自专栏郭耀华‘s Blog

剑指offer第二天

18.二叉树的镜像 操作给定的二叉树,将其变换为源二叉树的镜像。 ? /** public class TreeNode { int val = 0...

2596
来自专栏有趣的Python

5-玩转数据结构-链表与递归

前面我们实现了一个单链表,用它又实现了栈和队列,实现队列时对于链表进行了改进。链表与递归,递归和树联系在一起。但链表天然和递归有关,链表的递归学习会对后面我们理...

1371
来自专栏大闲人柴毛毛

动态规划法(二)——弗洛伊德算法

问题描述 给定一个带权有向图,计算任意两结点间的最短路径。 迪杰斯特拉算法可以计算指定起点到所有结点的最短路径长度,因此分别对每个结点使用一次迪杰斯特拉...

3717
来自专栏Java Edge

LinkedHashMap源码分析(基于Java8)概要示例代码节点构造函数增删查遍历

3815
来自专栏用户画像

7.4.2 选择排序之堆排序

堆排序是一个树形选择排序方法,它的特点是:在排序过程中,将L[1...n]看成是一棵完全二叉树的顺序存储结构,

554
来自专栏尾尾部落

[剑指offer] 最小的K个数

输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4。

762
来自专栏小樱的经验随笔

【Java学习笔记之十一】Java中常用的8大排序算法详解总结

分类: 1)插入排序(直接插入排序、希尔排序) 2)交换排序(冒泡排序、快速排序) 3)选择排序(直接选择排序、堆排序) 4)归并排序 5)分配排序(基...

3026
来自专栏小樱的经验随笔

平衡树初阶——AVL平衡二叉查找树+三大平衡树(Treap + Splay + SBT)模板【超详解】

平衡树初阶——AVL平衡二叉查找树 一、什么是二叉树 1. 什么是树。 计算机科学里面的树本质是一个树状图。树首先是一个有向无环图,由根节点指向子结点。但是不严...

2644
来自专栏平凡文摘

7大经典的排序算法总结实现

1132

扫码关注云+社区