针对非double和float类型的基本类型数组来说(文章中用int来举例),Arrays.sort直接进行快速排序,jdk源代码中的快速排序与我们平常看到的快速排序是不一样的,它对于普通的快速排序进行了优化。先看一下源代码,通过源代码来分析它是怎么优化的。

	public static void sort(int[] a) {
		sort1(a, 0, a.length);
	}

	private static void sort1(int x[], int off, int len) {
		// Insertion sort on smallest arrays
		// 如果长度小于7,就直接进行简单插入排序
		if (len < 7) {
			for (int i = off; i < len + off; i++)
				for (int j = i; j > off && x[j - 1] > x[j]; j--)
					swap(x, j, j - 1);
			return;
		}

		// Choose a partition element, v,m表示中间的那个位置
		int m = off + (len >> 1); // Small arrays, middle element
		// 如果长度在7和40之间的话,那么取   收尾中间 这三个数的中间值,下标分别是,l,m,n
		// 如果长度在40以上的话,取9个数的中间值,这九个下标分别对应
		// l,l+s,l + 2 * s,m - s,m, m + s,n - 2 * s, n - s, n
		if (len > 7) {
			int l = off;
			int n = off + len - 1;
			if (len > 40) { // Big arrays, pseudomedian of 9
				int s = len / 8;
				l = med3(x, l, l + s, l + 2 * s);
				m = med3(x, m - s, m, m + s);
				n = med3(x, n - 2 * s, n - s, n);
			}
			m = med3(x, l, m, n); // Mid-size, med of 3
		}
		//选定了pivot
		int v = x[m];

		// Establish Invariant: v* (<v)* (>v)* v*
		// 一趟快速排序下来将数组分成了四个区域  从左往右分别是    ==v,<v,>v,==v
		int a = off, b = a, c = off + len - 1, d = c;
		while (true) {
			while (b <= c && x[b] <= v) {
				if (x[b] == v)
					swap(x, a++, b);
				b++;
			}
			while (c >= b && x1 >= v) {
				if (x1 == v)
					swap(x, c, d--);
				c--;
			}
			if (b > c)
				break;
			swap(x, b++, c--);
		}

		// 分别将两端 ==v的数  交换到中间
		// Swap partition elements back to middle
		int s, n = off + len;
		s = Math.min(a - off, b - a);
		vecswap(x, off, b - s, s);
		s = Math.min(d - c, n - d - 1);
		vecswap(x, b, n - s, s);

		//交换完成后,数组状态为: <v,==v,>v
		// Recursively sort non-partition-elements
		if ((s = b - a) > 1)
			sort1(x, off, s);
		if ((s = d - c) > 1)
			sort1(x, n - s, s);
	}

通过代码分析,能看到的几个优化的地方分别是:
1:快速排序当数组长度缩小到7时,直接使用插入排序。

2:关于pivot值(中枢值)的选择,课本里常见的要么取数组第一个元素,要么取最后一个元素,这么取值的话很难做到均衡的划分,因为如果数组完全有序,这种方式效果跟冒泡并无太大区别,每次只能划出一个来。优化的话 有两种方式,一种是随机选取,即采用生成随机数的方式,效果可以,但是需要承担随机生成的时间消耗,另一种就是源代码中采取的,取中数的方式,即根据数组长度来做,当长度在7到40之间时,从首中尾三个位置中挑一个中间数作为pivot,而当长度大于40时,需要从9个数中选择pivot,即首中尾三个位置附近各挑三个数,一个九个数来找一个中间数。

3:关于相等的数的处理,即选定一个pivot后,对于数组中与pivot相等的数的处理,传统的方式是不处理,在划分时就是将数组划分成三部分,<V ,==V, >V,而源代码中处理方式是将数组划分为四个部分 ==V,<V, >V, ==V,划分成功后,再将两端的相等的数交换到中间,从而形成<V ,==V, >V的划分。

下面画个图说明一下程序的流程,假设数组初始时为:

init

 

根据代码我们可以知道,首先off=0,len=9,即数组从0开始,一共有9个元素,注意,最后一个下标为8

首先先确定pivot  需要从1,5,7中选择一个中间数作为pivot,即5。

然后进行快排,使用四个指针,abcd。根据代码可以知道这四个指针的用处,其中a和d用来处理相等的情况,b和c用来前后移动,具体逻辑可以看看代码很简单的。最后一趟快速排序跑完,数组的状态变成了:

first

其中可以看看每个指针的的作用了:

a-off = 2-0 = 2 表示左侧有2个与pivot相等

b-a = 5-2 = 3 表示有3个比pivot小

d-c = 7-4 = 3 表示有3个比pivot大

n-d-1 = 9-7-1 = 1 表示右侧有1个与pivot相等

最后就是把两端的相等的元素交换到中间。代码中s就是表示需要挪动几个位置,主要取决于a-off和b-a哪个小,另一侧也是一样。举个例子,比如数组为555551,我要把5换到中间,只需要换一个位置就行了,就是把首尾交换即可。代码里批量交换也是这个意思

交换完成后,数组的状态变成了:

final

接下来就要进行递归调用了,首先得判断小于大于pivot的数字,如果 b-a >1 表示至少有两个数小于pivot,所以还得递归,有一个就不用递归了。另一侧是一样的,d-c=3 >1 表示有3个数大于pivot,继续递归调用。所以,下一步就是分别排序  1,4,3  以及 9,7,6了。而一旦进入子递归调用时,他们的长度都小于7,所以会立即进行插入排序的。

推荐文章:

  1. 快速排序及优化:http://www.blogjava.net/killme2008/archive/2010/09/08/quicksort_optimized.html 系统的介绍了快速排序的优化,如果直接看本文有些困惑的话,可以看看这篇文章,里面详细的介绍了如果一步一步从最基本的快速排序最终优化到jdk源代码的过程。
  2. 坐在马桶上看算法:快速排序   http://developer.51cto.com/art/201403/430986.htm  这篇文章算是我在网上看到的 解释快排最清晰,最形象的了,而且图画的非常好,很容易理解。

jdk源码分析——Arrays.sort(4)_复杂对象采用归并排序

前面的博文介绍了基本数据类型在Arrsys.sort中是采用快速排序来处理的,具体参考前面的博文。而对于复杂对象(Object)来说,jdk Arrays.sort源码中是采用归...

阅读全文

jdk源码分析——Arrays.sort(3)_Double/float浮点数在快速排序中的特殊处理

前一篇文章    jdk源码分析——Arrays.sort(2)_快速排序的运用与优化  已经介绍过了对于int等基本数据类型 Arrays.sort中是如何进行排序的,这篇文章来介绍一下...

阅读全文

jdk源码分析——Arrays.sort(1)_概述

今后会发布一些分析jdk源码的文章,分析jdk源码有助于更好的理解java,这里也记录一下自己的学习过程,怕以后遗忘。 这次jdk的源码分析从Arrays.sort开始,...

阅读全文

欢迎留言