http://hxraid.iteye.com/blog/665095
【java.uti.Arrays】 包含用来操作数组(比如排序和搜索)的各种方法。这篇文章我们就来研究一些大师们写的排序算法。
(1) 基本数据类型数组的排序,如Arrays.sort(int[])等。采用了一种经 过调优的快速排序 。 该算法改编自 Jon L. Bentley 和 M. Douglas McIlroy 合著的 Engineering a Sort Function", Software-Practice and Experience Vol. 23(11) P. 1249-1265 (November 1993)。此算法在许多数据集上提供 n*log(n) 性能,这导致其他快速排序会降低二次型性能。
下面是JDK中调优快速排序算法的源代码:
/**
* 将指定范围的整形数组升序排序。
* x[] 待排数组
* off 从数组的第off个元素开始排序
* len 数组长度
*/
private static void sort1(int x[], int off, int len) {
//优化1:在小规模(size<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;
}
//优化2:精心选择划分元素,即枢轴
//如果是小规模数组(size<=7),直接取中间元素作为枢轴
//如果是中等规模数组(7=<size<=40),则在数组首、中、尾三个位置上的数中取中间大小的数作为枢轴
//如果是大规模数组(size>40),则在9个指定的数中取一个伪中数(中间大小的数s)
int m = off + (len >> 1);
if (len > 7) {
int l = off;
int n = off + len - 1;
if (len > 40) {
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);
}
int v = x[m];
//优化3:每一次枢轴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 && x[c] >= v) {
if (x[c] == v)
swap(x, c, d--);
c--;
}
if (b > c)
break;
swap(x, b++, c--);
}
//阶段二,将枢轴和与枢轴相等的元素交换到数组中间
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);
//阶段三,递归排序与枢轴不相等都元素区间
if ((s = b-a) > 1)
sort1(x, off, s);
if ((s = d-c) > 1)
sort1(x, n-s, s);
}
★ 优化1:在小规模(size<7)数组中,直接插入排序的效率要比快速排序高。
没有一种排序在任何情况下都是最优的《基于比较的内部排序总结 》。 O(N^2)级别的排序看起来似乎比所有先进排序要差的多。但实际上也并非如此,Arrays中的sort()算法就给了我们一个很好的例子。当待排数组规模非常小的时候(JDK中规模的阈值为INSERTIONSORT_THRESHOLD=7),直接插入排序反而要比快排,归并排序要好。
这个道理很简单。数组规模小,简单算法的比较次数不会比先进算法多多少。相反,诸如快排,归并排序等先进算法使用递归操作,所付出的运行代价更高。
★ 优化2:精心选择划分元素,即枢轴。
快排有一种最差的情况,即蜕化成效率最差的起跑排序(见《 交换排序 》)。 导致这种情况产生的主要原因就是枢轴的选择并不能把整个数组划分成两个大致相等的部分。比如对于基本有序的数组,选择第一个元素作为枢轴就会产生这种蜕化。
既然如此,我们可以看看Arryas.sort()是如何为我们选择枢轴的。
● 如果是小规模数组(size<=7),直接取中间元素作为枢轴。
● 如果是中等规模数组(7=<size<=40),则在数组首、中、尾三个位置上的数中取中间大小的数作为枢轴
● 如果是大规模数组(size>40),则在9个指定的数中取一个伪中数(中间大小的数s)
中小规模时,这种取法尽量可以避免数组的较小数或者较大数成为枢轴。值得一提的是大规模的时候,首先在数组中寻找9个数据(可以通过源代码发现这9个数据的位置较为平均的分布在整个数组上);然后每3个数据找中位数;最后在3个中位数上再找出一个中位数作为枢轴。
仔细想想,这种精心选择的枢轴,使得快排的最差情况成为了极小概率事件了。
★ 优化3:根据枢轴v划分,形成一个形如 (<v)* v* (>v)* 的数组
普通快排算法,都是使得枢轴元素移动到数组的较中间位置。枢轴之前的元素全部小于或等于枢轴,之后的元素全部大于枢轴。但与枢轴相等的元素并不能移动到枢轴附近位置。这一点在Arrays.sort()算法中有很大的优化。
我们举个例子来说明Arrays的优化细节 15、93、15、41、6、15、22、7、15、20
第一次枢轴:v=15
阶段一,形成 v* (<v)* (>v)* v* 的数组:
15、15、 7、6、 41、20、22、93、 15、15
我们发现,与枢轴相等的元素都移动到了数组的两边。而比枢轴小的元素和比枢轴大的元素也都区分开来了。
阶段二,将枢轴和与枢轴相等的元素交换到数组中间的位置上
7、6、 15、15、 15、15、 41、20、22、93
阶段三,递归排序与枢轴不相等都元素区间{7、6}和{41、20、22、93}
仔细想想,对于重复元素较多的数组,这种优化无疑能到达更好的效率。
(1) 对象数组的排序,如Arrays.sort(Object[])等。采用了一种经 过修改的归并排序 。 其也有几个优化的闪光点。
下面是JDK中改进归并排序算法的源代码:
/**
* 将指定范围的对象数组按自然顺序升序排序。
* src[] 原待排数组
* dest[] 目的待排数组
* low 待排数组的下界位置
* high 待排数组的上界位置
* off 从数组的第off个元素开始排序
*/
private static void mergeSort(Object[] src,
Object[] dest,
int low,
int high,
int off) {
int length = high - low;
//优化1:规模很小的数组的排序,直接插入排序的效率反而比归并要高。
//规模定在INSERTIONSORT_THRESHOLD=7之内
if (length < INSERTIONSORT_THRESHOLD) {
for (int i=low; i<high; i++)
for (int j=i; j>low &&
((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
swap(dest, j, j-1);
return;
}
// 递归排序dest的一半元素并赋值给src
int destLow = low;
int destHigh = high;
low += off;
high += off;
int mid = (low + high) >> 1;
mergeSort(dest, src, low, mid, -off);
mergeSort(dest, src, mid, high, -off);
//优化2:如果低子列表中的最高元素小于高子列表中的最低元素,则忽略合并
//如果需要归并的两端low~(middle-1),middle~high已经有序,即src[mid-1]==src[mid]。
//那么只需要将src的low~high赋值对应的dest即可,无需再归并。
if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {
System.arraycopy(src, low, dest, destLow, length);
return;
}
//将src的两个部分合并,并赋值给dest
for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)
dest[i] = src[p++];
else
dest[i] = src[q++];
}
}
★ 优化1: 同上面的快速排序
★ 优化2: 如果低子列表中的最高元素小于高子列表中的最低元素,则忽略合并。 这个优化措施无疑对基本有序序列是极大的效率改进。
分享到:
相关推荐
本文通过对数据压缩算法的简要介绍,然后以详细的示例演示了利用java.util.zip包实现数据的压缩与解压,并扩展到在网络传输方面如何应用java.util.zip包现数据压缩与解压
1. java.util.concurrent - Java 并发工具包 2. 阻塞队列 BlockingQueue 3. 数组阻塞队列 ArrayBlockingQueue 4. 延迟队列 DelayQueue 5. 链阻塞队列 LinkedBlockingQueue 6. 具有优先级的阻塞队列 ...
java.util.ConcurrentModificationException 异常问题详解1
详细介绍了java.util.logging.Logger的用法和结构,对如果扩展Logger起到抛砖引玉的作用!尊重劳动成果,亲下载了要给个评价!
Tomcat内存溢出的解决方法(java.util.concurrent.ExecutionException:java.lang.OutOfMemoryError),内附解决方案!
Exception in thread “main“ java.util.InputMismatchException
java.util.Date与java.sql.Date互转及字符串转换为日期时间格式.docx
java.util.concurrent系列文章(1) java.util.concurrent系列文章(1) java.util.concurrent系列文章(1) java.util.concurrent系列文章(1)
java并发工具包 java.util.concurrent中文版-带书签版
详细介绍java.util.Date和java.sql.Date相互转换的多种方法总结,希望对大家有帮助
这是我在编写struts2中遇到的问题,整理出来,包括截图,希望可以帮到大家
java.util包
世界范围内的时区列表。由 java.util.TimeZone 类导出
java.util.pdf
java.util包源码,pdf版,方便打印
使用java.util.timer实现的简单定时任务,在实现简单一次性定时任务时,使用java.util.timer非常的简单易用,适合没有接触过quartz的新手急用。
java.util.concurrent - Java 并发工具包 2. 阻塞队列 BlockingQueue 3. 数组阻塞队列 ArrayBlockingQueue 4. 延迟队列 DelayQueue 5. 链阻塞队列 LinkedBlockingQueue 6. 具有优先级的阻塞队列 ...
java.util包总结,方便大家学习。请多指教。
java.util.concurrent总体概览图。 收取资源分3分。需要的同学可以下载一下。 java.util.concurrent主要包括5个部分executor,colletions,locks,atomic,tools。 该图详细的列举了并发包下面的结构,包含所有接口和...
Java.util包常用接口