?
结果：
2097151
合并排序执行时间：443
合并排序递归树深度：4194301
快速排序执行时间：207
快速排序递归树深度：2795757
?
?
package com.zte.it.study.sort;
?
import java.util.Arrays;
?
/**
?* 类名: 排序算法比较 <br/>
?* 功能: TODO ADD FUNCTION. <br/>
?* 时间：2015-3-6 下午6:55:52
?*?
?* @author 10156351
?* @version
?* @since JDK 1.6
?*/
public class 排序算法比较
{
? ? static int recursive = 0;
?
? ? /**
? ? ?* main:(这里用一句话描述这个方法的作用). <br/>
? ? ?*?
? ? ?* @author 10156351
? ? ?* @param args
? ? ?* @since JDK 1.6
? ? ?*/
? ? public static void main(String[] args)
? ? {
? ? ? ? int num = Integer.MAX_VALUE >> 10;
? ? ? ? System.out.println(num);
? ? ? ? int[] array = new int[num];
? ? ? ? int[] array2 = new int[num];
? ? ? ? int[] array3 = new int[num];
? ? ? ? int[] array4 = new int[num];
? ? ? ? for (int i = 0; i < num; i++)
? ? ? ? {
? ? ? ? ? ? array[i] = (int) (Math.random() * Integer.MAX_VALUE);
? ? ? ? ? ? array2[i] = array[i];
? ? ? ? ? ? array3[i] = array[i];
? ? ? ? ? ? array4[i] = array[i];
? ? ? ? }
? ? ? ? long startTime = System.currentTimeMillis();
? ? ? ? recursive = 0;
? ? ? ? mergeSort(array);
? ? ? ? System.out.println("合并排序执行时间：" + (System.currentTimeMillis() - startTime));
? ? ? ? System.out.println("合并排序递归树深度：" + recursive);
?
? ? ? ? //
? ? ? ? startTime = System.currentTimeMillis();
? ? ? ? recursive = 0;
? ? ? ? quicksort(array2, 0, num - 1);
? ? ? ? System.out.println("快速排序执行时间：" + (System.currentTimeMillis() - startTime));
? ? ? ? System.out.println("快速排序递归树深度：" + recursive);
?
? ? ? ? // startTime = System.currentTimeMillis();
? ? ? ? // recursive = 0;
? ? ? ? // quickSort2(array3, 0, num - 1);
? ? ? ? // System.out.println("快速排序执行时间：" + (System.currentTimeMillis() - startTime));
? ? ? ? // System.out.println("快速排序递归树深度：" + recursive);
? ? ? ? //
? ? ? ? // startTime = System.currentTimeMillis();
? ? ? ? // recursive = 0;
? ? ? ? // quickSort3(array4, 0, num - 1);
? ? ? ? // System.out.println("快速排序执行时间：" + (System.currentTimeMillis() - startTime));
? ? ? ? // System.out.println("快速排序递归树深度：" + recursive);
?
// ? ? ? ?for (int i = 0; i < num / 1024; i++)
// ? ? ? ?{
// ? ? ? ? ? ?System.out.print(array2[i] + " ? ?");
// ? ? ? ? ? ?if (i % 20 == 19)
// ? ? ? ? ? ? ? ?System.out.println(array2[i]);
// ? ? ? ?}
? ? }
?
? ? public static void quicksort(int[] v, int left, int right)
? ? {
? ? ? ? recursive++;
? ? ? ? if (left < right)
? ? ? ? {
? ? ? ? ? ? int key = v[left];
? ? ? ? ? ? int low = left;
? ? ? ? ? ? int high = right;
? ? ? ? ? ? while (low < high)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? while (low < high && v[high] > key)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? high--;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? if (low < high)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? v[low] = v[high];
? ? ? ? ? ? ? ? ? ? low++;
? ? ? ? ? ? ? ? }
?
? ? ? ? ? ? ? ? while (low < high && v[low] < key)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? low++;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? if (low < high)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? v[high] = v[low];
? ? ? ? ? ? ? ? ? ? high--;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? ? ? v[low] = key;
? ? ? ? ? ? quicksort(v, left, low - 1);
? ? ? ? ? ? quicksort(v, low + 1, right);
? ? ? ? }
? ? }
?
? ? public static int[] quickSort2(int[] targetArr, int start, int end)
? ? {
? ? ? ? recursive++;
? ? ? ? int i = start + 1, j = end;
? ? ? ? int key = targetArr[start];
? ? ? ? if (start >= end)
? ? ? ? ? ? return targetArr;
?
? ? ? ? /*
? ? ? ? ?* 从i++和j--两个方向搜索不满足条件的值并交换
? ? ? ? ?*?
? ? ? ? ?* 条件为：i++方向小于key，j--方向大于key
? ? ? ? ?*/
? ? ? ? while (true)
? ? ? ? {
? ? ? ? ? ? while (targetArr[j] > key)
? ? ? ? ? ? ? ? j--;
? ? ? ? ? ? while (targetArr[i] < key && i < j)
? ? ? ? ? ? ? ? i++;
? ? ? ? ? ? if (i >= j)
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? swap(targetArr, i, j);
? ? ? ? ? ? if (targetArr[i] == key)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? j--;
? ? ? ? ? ? }
? ? ? ? ? ? else
? ? ? ? ? ? {
? ? ? ? ? ? ? ? i++;
? ? ? ? ? ? }
? ? ? ? }
?
? ? ? ? /* 关键数据放到‘中间’ */
? ? ? ? swap(targetArr, start, j);
?
? ? ? ? if (start < i - 1)
? ? ? ? {
? ? ? ? ? ? quickSort2(targetArr, start, i - 1);
? ? ? ? }
? ? ? ? if (j + 1 < end)
? ? ? ? {
? ? ? ? ? ? quickSort2(targetArr, j + 1, end);
? ? ? ? }
?
? ? ? ? return targetArr;
? ? }
?
? ? public static void quickSort3(int[] targetArr, int start, int end)
? ? {
? ? ? ? recursive++;
? ? ? ? int i = start, j = end;
? ? ? ? int key = targetArr[start];
?
? ? ? ? while (i < j)
? ? ? ? {
? ? ? ? ? ? /* 按j--方向遍历目标数组，直到比key小的值为止 */
? ? ? ? ? ? while (j > i && targetArr[j] >= key)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? j--;
? ? ? ? ? ? }
? ? ? ? ? ? if (i < j)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? /* targetArr[i]已经保存在key中，可将后面的数填入 */
? ? ? ? ? ? ? ? targetArr[i] = targetArr[j];
? ? ? ? ? ? }
? ? ? ? ? ? /* 按i++方向遍历目标数组，直到比key大的值为止 */
? ? ? ? ? ? while (i < j && targetArr[i] <= key)
? ? ? ? ? ? /* 此处一定要小于等于零，假设数组之内有一亿个1，0交替出现的话，而key的值又恰巧是1的话，那么这个小于等于的作用就会使下面的if语句少执行一亿次。 */
? ? ? ? ? ? {
? ? ? ? ? ? ? ? i++;
? ? ? ? ? ? }
? ? ? ? ? ? if (i < j)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? /* targetArr[j]已保存在targetArr[i]中，可将前面的值填入 */
? ? ? ? ? ? ? ? targetArr[j] = targetArr[i];
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? /* 此时i==j */
? ? ? ? targetArr[i] = key;
?
? ? ? ? if (i - start > 1)
? ? ? ? {
? ? ? ? ? ? /* 递归调用，把key前面的完成排序 */
? ? ? ? ? ? quickSort3(targetArr, start, i - 1);
? ? ? ? }
? ? ? ? if (end - j > 1)
? ? ? ? {
? ? ? ? ? ? /* 递归调用，把key后面的完成排序 */
? ? ? ? ? ? quickSort3(targetArr, j + 1, end);
? ? ? ? }
? ? }
?
? ? public static void swap(int[] arr, int start, int end)
? ? {
? ? ? ? int tmp = arr[start];
? ? ? ? arr[start] = arr[end];
? ? ? ? arr[end] = tmp;
? ? }
?
? ? public static void mergeSort(int[] array)
? ? {
? ? ? ? recursive++;
? ? ? ? int length = array.length;
? ? ? ? int middle = length / 2;
?
? ? ? ? if (length > 1)
? ? ? ? {
?
? ? ? ? ? ? int[] left = Arrays.copyOfRange(array, 0, middle);// 拷贝数组array的左半部分
? ? ? ? ? ? int[] right = Arrays.copyOfRange(array, middle, length);// 拷贝数组array的右半部分
? ? ? ? ? ? mergeSort(left);// 递归array的左半部分
? ? ? ? ? ? mergeSort(right);// 递归array的右半部分
? ? ? ? ? ? merge(array, left, right);// 数组左半部分、右半部分合并到Array
? ? ? ? }
? ? }
?
? ? // 合并数组，升序
? ? private static void merge(int[] result, int[] left, int[] right)
? ? {
?
? ? ? ? int i = 0, l = 0, r = 0;
?
? ? ? ? while (l < left.length && r < right.length)
? ? ? ? {
?
? ? ? ? ? ? if (left[l] < right[r])
? ? ? ? ? ? {
? ? ? ? ? ? ? ? result[i] = left[l];
? ? ? ? ? ? ? ? i++;
? ? ? ? ? ? ? ? l++;
? ? ? ? ? ? }
? ? ? ? ? ? else
? ? ? ? ? ? {
? ? ? ? ? ? ? ? result[i] = right[r];
? ? ? ? ? ? ? ? i++;
? ? ? ? ? ? ? ? r++;
? ? ? ? ? ? }
? ? ? ? }
?
? ? ? ? while (r < right.length)
? ? ? ? {// 如果右边剩下合并右边的
? ? ? ? ? ? result[i] = right[r];
? ? ? ? ? ? r++;
? ? ? ? ? ? i++;
? ? ? ? }
?
? ? ? ? while (l < left.length)
? ? ? ? {
? ? ? ? ? ? result[i] = left[l];
? ? ? ? ? ? l++;
? ? ? ? ? ? i++;
? ? ? ? }
? ? }
}
?
原文：http://javaprimary.iteye.com/blog/2190228