关于 Quick Sort 和 MergeSort 的实验

Question

前几天看到关于 java.util.Arrays 里面的 sort 方法的讨论。产生了对 Quick Sort 和 Merge Sort 的排序时间进行比较的想法。先是找了一些关于排序的资料，发现下面的链接上有比较全的排序算法，还有很直观的演示（好像也是用了 java 自带的 SortItem 类和其他两个类）。从演示看来， Quick Sort 的速度那真是嗖嗖的。比 Merge Sort 快多了。
请参考：http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html。然后又看了看 java.util.Arrays 里面关于 sort(int[] src) 和 sort( object[] src) 的代码，将之修改为都可以针对我设定的 SortElement 类型数字进行排序。其中 SortElement 的 getValue 方法作了一个可以设置的固定延时，来模拟各种情况下 object 类型的元素比较所需的时间。发现在大多数情况下， Merge Sort 都比 Quick Sort 快。尤其是数组长度较大，比较所需时间较长的情况下， Merge Sort 的表现会更好。还有在下面的链接中，一种 Shear Sort 的并行排序算法，看上去也很快。http://www.cs.rit.edu/~atk/Java/Sorting/sorting.html

Answer 1

下面是我试验用的代码，明天改成对 int[] 排序来对比一下两种排序方法的速度。
/**
 * @author Owen Luo
 * @version Created at 2008-11-25 下午08:48:07
 */public class CSDN_SortTest { public static void main(String[] args) {
// TODO Auto-generated method stub int delay = 10;
int length = 1000; SortElement[] forQuick;
SortElement[] forMerge;
SortElement[] forMergeDes; CSDN_SortTest test = new CSDN_SortTest(); for (int i = 1; i < 6; i++) {
forQuick = test.genArray(length, delay * i);
forMerge = test.copyArray(forQuick);
forMergeDes = test.copyArray(forQuick); for (SortElement q : forQuick) {
System.out.print(q.getValue() + " ");
}
System.out.println(); for (SortElement q : forMerge) {
System.out.print(q.getValue() + " ");
}
System.out.println(); long startTime;
long timeCost;
startTime = System.nanoTime();
test.QuickSort(forQuick, 0, forQuick.length);
timeCost = System.nanoTime() - startTime;
System.out.println("This is #" + i + ",delay " + i * delay
+ " nano seconds for getValue");
System.out.println("QuickSort takes " + timeCost + " nano seconds"); startTime = System.nanoTime();
test.MergeSort(forMerge, forMergeDes, 0, forMerge.length, 0);
timeCost = System.nanoTime() - startTime;
System.out.println("This is #" + i + ",delay " + i * delay
+ " nano seconds for getValue");
System.out.println("MergeSort takes " + timeCost + " nano seconds"); for (SortElement q : forQuick) {
System.out.print(q.getValue() + " ");
}
System.out.println(); for (SortElement q : forMergeDes) {
System.out.print(q.getValue() + " ");
}
System.out.println();
System.out.println(); } } /**
 * QuickSort is picked from java.util.Arrays, original name is sort1(...)
 * And modified to suitable for my customized class SortElement Sorts the
 * specified sub-array of integers into ascending order.
 */
private static void QuickSort(SortElement x[], int off, int len) {
// Insertion sort on smallest arrays if (len < 7) {
for (int i = off; i < len + off; i++)
for (int j = i; j > off
&& x[j - 1].getValue() > x[j].getValue(); j--)
swap(x, j, j - 1);
return;
} // 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
}
SortElement v = x[m]; // Establish Invariant: v* (<v)* (>v)* v*
int a = off, b = a, c = off + len - 1, d = c;
while (true) {
while (b <= c && x[b].getValue() <= v.getValue()) {
if (x[b] == v)
swap(x, a++, b);
b++;
}
while (c >= b && x[c].getValue() >= v.getValue()) {
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)
QuickSort(x, off, s);
if ((s = d - c) > 1)
QuickSort(x, n - s, s);
} /**
 * Swaps x[a] with x[b].
 */
private static void swap(SortElement x[], int a, int b) {
SortElement t = x[a];
x[a] = x[b];
x[b] = t;
} /**
 * Swaps x[a .. (a+n-1)] with x[b .. (b+n-1)].
 */
private static void vecswap(SortElement x[], int a, int b, int n) {
for (int i = 0; i < n; i++, a++, b++)
swap(x, a, b);
} /**
 * Returns the index of the median of the three indexed integers.
 */
private static int med3(SortElement x[], int a, int b, int c) {
return (x[a].getValue() < x[b].getValue() ? (x[b].getValue() < x[c]
.getValue() ? b : x[a].getValue() < x[c].getValue() ? c : a)
: (x[b].getValue() > x[c].getValue() ? b
: x[a].getValue() > x[c].getValue() ? c : a));
} /**
 * Tuning parameter: list size at or below which insertion sort will be used
 * in preference to mergesort or quicksort. 
 * 很奇怪，quicksort 里面没有用到这个常量，而是直接用了数值 7。
 */
private static final int INSERTIONSORT_THRESHOLD = 7; /**
 * Src is the source array that starts at index 0 Dest is the (possibly
 * larger) array destination with a possible offset low is the index in dest
 * to start sorting high is the end index in dest to end sorting off is the
 * offset to generate corresponding low, high in src
 */
private static void MergeSort(SortElement[] src, SortElement[] dest,
int low, int high, int off) {
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
&& (dest[j - 1]).getValue() > dest[j].getValue(); 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);
MergeSort(dest, src, mid, high, -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 (src[mid - 1].getValue() <= src[mid].getValue()) {
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
&& (src[p].getValue() <= src[q].getValue()))
dest[i] = src[p++];
else
dest[i] = src[q++];
}
} /**
 * Swaps x[a] with x[b].
 */ /**
 * same with quick sort swap 
 * private static void swap(SortElement[] x, int a, int b) {
 *  SortElement t = x[a];
 *  x[a]= x[b];
 *  x[b]=t;
 *  }
 */ // Initial a SortElement array for sort
private SortElement[] genArray(int length, int delayTime) {
SortElement[] src = new SortElement[length];
int[] intValue = new int[length];
for (int i = 0; i < length; i++) {
intValue[i] = i;
src[i] = new SortElement();
src[i].setDelay(delayTime);
} for (int i = 0, n = length; i < length; i++, n--) {
int r = (int) (Math.random() * n);
src[i].setValue(intValue[r]);
intValue[r] = intValue[n - 1];
}
return src;
} private SortElement[] copyArray(SortElement[] src) {
SortElement[] des = new SortElement[src.length];
for (int i = 0; i < src.length; i++) {
des[i] = new SortElement();
des[i].setValue(src[i].getValue());
des[i].setDelay(src[i].getDelay());
}
return des;
} // use a nested class here
class SortElement { int value; // value for sorting
int delayTime; // nano seconds to be delayed while getting value. long startTime; SortElement() { } public int getValue() { startTime = System.nanoTime(); while (System.nanoTime() < startTime + delayTime) {
} return value;
} public void setValue(int v) {
value = v;
} public void setDelay(int delay) {
delayTime = delay;
} public int getDelay() {
return delayTime;
} }}