Java-归并排序和快速排序的效率比较

public class MergeSort {

	public int[] A;

	public MergeSort(int[] array) {
		this.A = array.clone();
		sort(0, array.length - 1);
	}

	public void sort(int low, int high) {

		if (low < high) {
			int mid = (low + high) / 2;
			sort(low, mid);
			sort(mid + 1, high);
			merge(low, mid, high);
		}
	}

	public void merge(int low, int mid, int high) {

		// 声明新的数组，临时储存归并结果
		int[] B = new int[high - low + 1];
		int h = low;
		int i = 0;
		int j = mid + 1;

		while (h <= mid && j <= high) {
			if (A[h] <= A[j]) {
				B[i] = A[h];
				h++;
			} else {
				B[i] = A[j];
				j++;
			}
			i++;
		}

		// 等号很重要
		if (h <= mid) {
			for (int k = h; k <= mid; k++) {
				B[i] = A[k];
				i++;
			}
		} else {
			for (int k = j; k <= high; k++) {
				B[i] = A[k];
				i++;
			}
		}

		for (int k = low; k < high; k++) {
			A[k] = B[k - low];
		}

	}
}

public class QuickSort {

	public int[] A;

	public QuickSort(int[] array) {
		this.A = array.clone();
		sort(0, array.length - 2);
	}

	public void sort(int p, int q) {
		if (p < q) {
			int j = partition(p, q);
			sort(p, j - 1);
			sort(j + 1, q);
		}
	}

	public int partition(int p, int q) {
		int j = q;
		int axis = A[p];
		int i = p;

		while (true) {

			//从左往右找到第一个比axis大的数字
			while (A[i] <= axis) {
				i++;
			};

			//从右往左找到第一个小于等于axis的数字
			while (A[j] > axis) {
				j--;
			};

			if (i < j) {
				swap(i, j);
			} else {
				break;
			}
		}

		A[p] = A[j];
		A[j] = axis;

		return j;
	}

	public void swap(int i, int j) {
		int tmp = A[i];
		A[i] = A[j];
		A[j] = tmp;
	}

}

import java.util.Arrays;
import java.util.Random;

public class TimeCounter {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		int size = 101;
		int maximum = 100000;
		int[] array = new int[size];

		for (int i = 0; i < array.length - 1; i++) {
			array[i] = new Random().nextInt(maximum);
		}

		//快排数组中的最后一个数字最大
		array[size - 1] = maximum + 1;
 
		long QuickStart = System.currentTimeMillis();
		new QuickSort(array);
		long QuickEnd = System.currentTimeMillis();

		long MergeStart = System.currentTimeMillis();
		MergeSort mergesort=new MergeSort(array);
		long MergeEnd = System.currentTimeMillis();

//		 System.out.println(Arrays.toString(array));
//		 System.out.println(Arrays.toString(mergesort.A));

		System.out.println("quick sort: " + (QuickEnd - QuickStart));
		System.out.println("merge sort: " + (MergeEnd - MergeStart));

	}
}