我为QuickSort创建了一些改进,并决定针对Java Arrays.sort()进行测试.
结果令人着迷：
在Java 6上：
>我的时间/系统时间= 74/83 = 0.891566265060241
>我的时间/系统时间= 75/79 = 0.9493670886075949
>我的时间/系统时间= 75/84 = 0.8928571428571429
在Java 7上：
>我的时间/系统时间= 115/70 = 1.6428571428571428
>我的时间/系统时间= 101/76 = 1.3289473684210527
>我的时间/系统时间= 102/61 = 1.6721311475409837
正如您所看到的,我的算法在Java 6上的表现更好,但是我不明白它对Java 7的影响有多大.可能你能找到原因吗？
编辑：我的算法如何工作：
>步骤1：取3个数字,对它们进行排序,使用中间数字作为枢轴
>步骤2：将所有大于枢轴的数字向右移动,将所有数字小于向左旋转的数字,并将枢轴放置在已排序数组中的最终位置.这实际上是在O(N)中实现的.
>步骤3：递归地重复步骤1和2的左侧和右侧.当富集小于12个元素的子数组时,使用网络排序对其进行排序.
我的源代码
public class QuickSort {
public static void sort(int[] source) {
int buffer[] = new int[source.length];
concatenate(source, buffer, 0, source.length);
}
private static void concatenate(int[] source, int[] buffer, int low, int high) {
int count = high - low;
int lowBuffer = low;
int highBuffer = high;
if (count < 2) {
return;
}
if (count < 12) {
networkSort(source, buffer, low, count);
return;
}
int pivotIndex = bestOfThree(source, low);
int value = source[pivotIndex];
for (int i = low; i < high; i++) {
if (i == pivotIndex) {
continue;
}
if (source[i] < value) {
buffer[lowBuffer] = source[i];
source[lowBuffer] = buffer[lowBuffer];
lowBuffer++;
}
else {
highBuffer--;
buffer[highBuffer] = source[i];
}
}
buffer[lowBuffer] = source[lowBuffer] = value;
for (int i = lowBuffer; i < high; i++) {
source[i] = buffer[i];
}
concatenate(source, buffer, lowBuffer + 1, high);
concatenate(source, buffer, low, lowBuffer);
}
private static int bestOfThree(int[] source, int low) {
int a = low;
int b = a + 1;
int c = a + 2;
int median = -1;
if (source[a] >= source[b] && source[a] >= source[c]) {
if (source[b] < source[c]) {
median = c;
}
else {
median = b;
}
}
else if (source[b] >= source[a] && source[b] >= source[c]) {
if (source[a] < source[c]) {
median = c;
}
else {
median = a;
}
}
else if (source[c] >= source[a] && source[c] >= source[b]) {
if (source[a] < source[b]) {
median = b;
}
else {
median = a;
}
}
return median;
}
private static int[][] networkSort = {
{ 0, 1 },
{ 1, 2, 0, 2, 0, 1 },
{ 0, 1, 2, 3, 0, 2, 1, 3, 1, 2 },
{ 0, 1, 3, 4, 2, 4, 2, 3, 1, 4, 0, 3, 0, 2, 1, 3, 1, 2 },
{ 1, 2, 4, 5, 0, 2, 3, 5, 0, 1, 3, 4, 2, 5, 0, 3, 1, 4, 2, 4, 1, 3, 2, 3 },
{ 1, 2, 3, 4, 5, 6, 0, 2, 3, 5, 4, 6, 0, 1, 4, 5, 2, 6, 0, 4, 1, 5, 0, 3, 2, 5, 1, 3, 2, 4, 2, 3 },
{ 0, 1, 2, 3, 4, 5, 6, 7, 0, 2, 1, 3, 4, 6, 5, 7, 1, 2, 5, 6, 0, 4, 3, 7, 1, 5, 2, 6, 1, 4, 3, 6, 2, 4, 3, 5, 3, 4 },
{ 0, 1, 3, 4, 6, 7, 1, 2, 4, 5, 7, 8, 0, 1, 3, 4, 6, 7, 2, 5, 0, 3, 1, 4, 5, 8, 3, 6, 4, 7, 2, 5, 0, 3, 1, 4, 5, 7, 2, 6, 1, 3, 4, 6, 2, 4, 5, 6, 2, 3 },
{ 4, 9, 3, 8, 2, 7, 1, 6, 0, 5, 1, 4, 6, 9, 0, 3, 5, 8, 0, 2, 3, 6, 7, 9, 0, 1, 2, 4, 5, 7, 8, 9, 1, 2, 4, 6, 7, 8, 3, 5, 2, 5, 6, 8, 1, 3, 4, 7, 2, 3, 6, 7, 3, 4, 5, 6, 4, 5 },
{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 3, 5, 7, 0, 2, 4, 6, 8, 10, 1, 2, 5, 6, 9, 10, 0, 4, 3, 7, 1, 5, 6, 10, 4, 8, 5, 9, 2, 6, 0, 4, 3, 8, 1, 5, 6, 10, 2, 3, 8, 9, 1, 4, 7, 10, 3, 5, 6, 8, 2, 4, 7, 9, 5, 6, 3, 4, 7, 8 }
};
private static int tmp;
private static void networkSort(int[] source, int[] buffer, int low, int count) {
int[] networkData = networkSort[count - 2];
for (int i = 0; i < networkData.length; i += 2) {
int index1 = low + networkData[i];
int index2 = low + networkData[i + 1];
if (source[index1] > source[index2]) {
tmp = source[index1];
buffer[index1] = source[index1] = source[index2];
buffer[index2] = source[index2] = tmp;
}
}
}
}
基础测试课程
public abstract class Test {
protected int[][] buffer;
private final Random random = new Random();
public int numberOfTests = 100;
public int maxValue = 1000;
public int numberOfItems = 100;
protected void createBuffer() {
buffer = new int[numberOfTests][];
for (int i = 0; i < numberOfTests; i++) {
int[] list = new int[numberOfItems];
addRandomNumbers(list);
buffer[i] = list;
}
}
protected void createBuffer(int...parametes) {
buffer = new int[1][];
buffer[0] = parametes;
}
protected void addRandomNumbers(int[] list) {
for (int i = 0; i < numberOfItems; i++) {
int value = random.nextInt(maxValue);
list[i] = value;
}
}
protected int[][] cloneBuffer() {
int[][] clonedBuffer = new int[numberOfTests][];
for(int i = 0; i < buffer.length; i++){
int[] clonedList = new int[buffer[i].length];
int[] list = buffer[i];
for (int j = 0; j < list.length; j++) {
int element = list[j];
clonedList[j] = element;
}
clonedBuffer[i] = clonedList;
}
return clonedBuffer;
}
public abstract void test();
}
性能测试
public class PerformanceTest extends Test {
private final Timer timer = new Timer();
public void test() {
createBuffer();
timer.reset();
testSystem();
timeResoult("System");
timer.reset();
testMy();
timeResoult("My List");
}
public void test(int numberOfTests) {
long myTotalTime = 0;
long systemTotalTime = 0;
for (int i = 0; i < numberOfTests; i++) {
createBuffer();
timer.reset();
testSystem();
long systemTime = timeResoult();
systemTotalTime += systemTime;
timer.reset();
testMy();
long myTime = timeResoult();
myTotalTime += myTime;
System.out.println("My Time / System Time = " + myTime + " / " + systemTime + " = \t"
+ ((double) myTime / systemTime));
}
System.out.println("My Time / System Time = " + ((double) myTotalTime / systemTotalTime));
}
private long timeResoult() {
return timeResoult(null);
}
private long timeResoult(String source) {
long time = timer.check();
if (source != null) {
System.out.println(source + ">\tTime: " + time);
}
return time;
}
private void testMy() {
int[][] buffer = cloneBuffer();
for (int i = 0; i < numberOfTests; i++) {
int[] list = buffer[i];
QuickSort.sort(list);
}
}
private void testSystem() {
int[][] buffer = cloneBuffer();
for (int i = 0; i < numberOfTests; i++) {
int[] list = buffer[i];
Arrays.sort(list);
}
}
}
主要
public static void main(String[] args) {
PerformanceTest testBasics = new PerformanceTest();
testBasics.numberOfTests = 1000;
testBasics.numberOfItems = 1000;
testBasics.maxValue = 1000000;
testBasics.test(100);
}
解决方法:
他们为Java 7改变了Arrays.sort的排序算法.对于排序对象,Arrays.sort现在使用称为Timsort的算法和基于原始的双枢轴快速排序.更多信息在这answer.
如果你真的想使用旧的,显然你可以设置一个系统属性java.util.Arrays.useLegacyMergeSort.
见Java 7 compatibility documentation.