日期:2014-05-20 浏览次数:20884 次
package com.algorithm; import java.util.Arrays; public class SortRunner { public static void main(String args[]) { // int data[] = new int[] { 12, 5, 9, 8, 16, 3, 1, 7, 4, 0, 11, 2, // 19, // 14, 13, 15, 6, 18, 20, 17, 10 }; long baseSize = 1000000L; int n = (int) (Math.random() * baseSize); int[] data = new int[n]; for (int i = 0; i < n; i++) { data[i] = (int) (Math.random() * baseSize); } int[] commonData = data.clone(); long commonBefore = System.currentTimeMillis(); // commonSort(commonData); long commonAfter = System.currentTimeMillis(); System.out.println("CommonSort " + (commonAfter - commonBefore)); int[] quickData = data.clone(); long quickBefore = System.currentTimeMillis(); quickSort(quickData, 0, quickData.length - 1); long quickAfter = System.currentTimeMillis(); System.out.println("QuickSort " + (quickAfter - quickBefore)); int[] shellData = data.clone(); long shellBefore = System.currentTimeMillis(); shellSort(shellData); long shellAfter = System.currentTimeMillis(); System.out.println("ShellSort " + (shellAfter - shellBefore)); int[] mergeData = data.clone(); long mergeBefore = System.currentTimeMillis(); mergeSort(mergeData, 0, mergeData.length - 1); long mergeAfter = System.currentTimeMillis(); System.out.println("MergeSort " + (mergeAfter - mergeBefore)); int[] heapData = data.clone(); long heapBefore = System.currentTimeMillis(); heapSort(heapData); long heapAfter = System.currentTimeMillis(); System.out.println("HeapSort " + (heapAfter - heapBefore)); System.out.println(); // print(data); // print(commonData); // print(quickData); // print(shellData); // print(mergeData); // print(heapData); } /** * 冒泡排序 */ public static void commonSort(int[] data) { for (int i = 0; i < data.length; i++) { for (int j = 0; j < i; j++) { if (data[j] > data[i]) { int temp = data[j]; data[j] = data[i]; data[i] = temp; } } } } /** * 快速排序 */ public static void quickSort(int[] data, int left, int right) { if (left >= right) { return; } int n = data[left]; int l = left; int r = right; while (l < r) { while (data[r] >= n && l < r) { --r; } data[l] = data[r]; while (data[l] <= n && l < r) { ++l; } data[r] = data[l]; } data[r] = n; quickSort(data, left, r - 1); quickSort(data, r + 1, right); } /** * 希尔排序 */ public static void shellSort(int[] data) { int length = data.length; int n = length; while ((n = n / 2) >= 1) { for (int i = 0; i < n; i++) { for (int j = i; j < length; j += n) { int k = j; while (k >= 0 && k + n < length && data[k] > data[k + n]) { int temp = data[k + n]; data[k + n] = data[k]; data[k] = temp; k -= n; } } } } } /** * 合并排序 */ public static void mergeSort(int[] data, int left, int right) { if (left >= right) { return; } int middle = (left + right) / 2; mergeSort(data, left, middle); mergeSort(data, middle + 1, right); int[] temp = new int[right - left + 1]; int i = left; int j = middle + 1; int k = 0; while (k <= right) { if (i > middle) { while (j <= right) { temp[k++] = data[j++]; } break; } else if (j > right) { while (i <= middle) { temp[k++] = data[i++]; } break; } if (data[i] < data[j]) { temp[k++] = data[i++]; } else { temp[k++] = data[j++]; } } k = 0; for (i = left; i <= right; i++) { data[i] = temp[k++]; } } /** * 堆排序 */ public static void heapSort(int[] data) { int length = data.length; // 建堆 for (int i = length / 2 - 1; i >= 0; i--) { adjustHeap(i, data, length); } for (int i = length - 1; i >= 0; i--) { int temp = data[0]; data[0] = data[i]; data[i] = temp; adjustHeap(0, data, i); } } private static void adjustHeap(int parent, int[] data, int length) { int left = parent * 2 + 1; int right = left + 1; int max_index = parent; if (left < length && data[left] > data[max_index]) { max_index = left; } if (right < length && data[right] > data[max_index]) { max_index = right; } if (max_index != parent) { int temp = data[parent]; data[parent] = data[max_index]; data[max_index] = temp; adjustHeap(max_index, data, length); } } public static void print(int[] data, int left, int right) { for (int i = left; i <= right; i++) { System.out.print(data[i] + " "); } int[] array = new int[] { 1, 2, 3, 4 }; Arrays.sort(array); System.out.println(); } public static void print(int[] data) { for (int i = 0; i < data.length; i++) { System.out.print(data[i] + " "); } System.out.println(); } }