Arrays.sort算法

Arrays.sort(int[] i) 的算法总体思路
如果元素小于7个使用一般排序
  否则使用快速排序。在快速排序中递归调用Arrays.sort(int[] i) 方法。


其中一般排序的思路：
采用双循环。
每次外层循环(第N次)处理完后都保证从左到右(第1到N个)已经排好序，
内层循环处理时只处理第1到第N个元素)
    如果发现最右侧的元素比它的左邻居还要大即可直接跳出内层循环。
    否则将从左向右逐个和最右侧的元素比对，发现有元素比最右侧的元素大就对换。

引用

	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;
	}

比如[3,2,1,5,0]的排序过程
首先对[3,2]排序
[2,3,1,5,0]
对[2,3,1]排序
[1,3,2,5,0]
[1,2,3,5,0]下一步会对[1,2,3,5]进行排序
此时发现 5比3大则直接跳出内层循环。下一步会对[1,2,3,5,0]排序
[0,2,3,5,1]
[0,1,3,5,2]
[0,1,2,5,3]
[0,1,2,3,5]


快速排序的思路其实不难，但是看其实现的代码看了老半天。

快速排序思路:
在数组中找一个中间值元素(Arrays.sort方法在找中间值的处理上也考虑的比较多)，最好是整个序列中值不大不小的那个元素。
然后让中间值元素左边的都比它小，中间值元素右边的都比它大，相等的元素放到中间值旁边。
这样处理一次后就可以保证左边的序列都是较小的，右边的序列都是较大的。
然后分别对左边和后边的序列进行递归处理。

Arrays.sort方法找中间值：
如果序列长度大于7小于41则从首、尾、中间三个元素中挑一个中间值
如果序列长度大于40个，则将序列大致分三段，每一段按上面的方法各取一个中间值，然后在这三个中间值中取一次中间值。

引用

	// Choose a partition element, v
	int m = off + (len >> 1);       // Small arrays, middle element
	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
	}
	int v = x[m];

Arrays.sort方法中快速排序部分的元素移动：
就像两只部队从序列两端分别向中间移动。
  首先从左向右移动
    如果遇到和中间值相等的元素则将其尽可能向左排，
    如果遇到小于中间值的元素则继续向右查找，如果和从右向左的部队会师就停下来。
    如果遇到大于中间值的元素则记下该元素假设为X，然后等待从右向左的运行结果。
  从右向左移动
    如果遇到和中间值相等的元素则将其尽可能向右排，
    如果遇到大于中间值的元素则继续向左查找，如果和从左向右的部队会师就停下来。
    如果遇到小于中间值的元素则记下该元素假设为Y。
  如果两个方向的部队没有会师，交换X,Y元素，然后两支部队按照上面逻辑继续相向运动。
  如果已经会师则将左右两端和中间值相等的元素放到序列的中间。
现在就已经完成了一轮次的快速排序了。剩下的就是对中间值左右两边的两个序列分别做同样的动作(递归)。

引用

// Establish Invariant: 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 && x[c] >= v) {
		if (x[c] == v)
		    swap(x, c, d--);
		c--;
	    }
	    if (b > c)
		break;
	    swap(x, b++, c--);
	}

	// 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);//将右边的和中间值相等的元素移到序列中间

	// Recursively sort non-partition-elements
	if ((s = b-a) > 1)
	    sort1(x, off, s);
	if ((s = d-c) > 1)
	    sort1(x, n-s, s);