/** * 冒泡排序 */ private void bubblesort(int[] arr) { for (int i = arr.length; i > 0; i--) { for (int j = arr.length - 1; j > arr.length - i; j--) { if (arr[j] < arr[j - 1]) { int temp = arr[j]; arr[j] = arr[j - 1]; arr[j - 1] = temp; } } } }
/** * 快速排序 */ private void qsort(int[] arr, int head, int tail) { if (arr == null || head >= tail || arr.length == 0) { return; } int i = head, j = tail, q = arr[(i + j) / 2]; while (i < j) { while (arr[i] < q) { ++i; } while (arr[j] > q) { --j; } if (i < j) { int temp = arr[j]; arr[j] = arr[i]; arr[i] = temp; ++i; --j; } else if (i == j) { ++i; } } qsort(arr, head, j); qsort(arr, i, tail); }
static void merge_sort_recursive(int[] arr, int[] result, int start, int end) { if (start >= end) return; int len = end - start, mid = (len >> 1) + start; int start1 = start, end1 = mid; int start2 = mid + 1, end2 = end; merge_sort_recursive(arr, result, start1, end1); merge_sort_recursive(arr, result, start2, end2); int k = start; while (start1 <= end1 && start2 <= end2) result[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++]; while (start1 <= end1) result[k++] = arr[start1++]; while (start2 <= end2) result[k++] = arr[start2++]; for (k = start; k <= end; k++) arr[k] = result[k]; } public static void merge_sort(int[] arr) { int len = arr.length; int[] result = new int[len]; merge_sort_recursive(arr, result, 0, len - 1); }
@test public void testspeed(){ random random = new random(); int arrs[] = new int[30000]; for (int i = 0; i < arrs.length; i++) { arrs[i] = random.nextint(10000); } int[] arrs2 = arrs.clone(); int[] arrs3 = arrs.clone(); int[] arrs4 = arrs.clone(); long start = system.currenttimemillis(); bubblesort(arrs); long end1 = system.currenttimemillis(); log.info("冒泡排序 time:{}ms",(end1-start)); qsort(arrs2,0,arrs2.length-1); long end2 = system.currenttimemillis(); log.info("快速排序 time:{}ms",(end2-end1)); merge_sort(arrs3); long end3 = system.currenttimemillis(); log.info("归并排序 time:{}ms",(end3-end2)); arrays.sort(arrs4); long end4 = system.currenttimemillis(); log.info("java.util排序 time:{}ms",(end4-end3)); }
15:35:28.609 [main] info com.zhiyis.framework.learn.sort.testsort - 冒泡排序 time:8497ms 15:35:28.645 [main] info com.zhiyis.framework.learn.sort.testsort - 快速排序 time:40ms 15:35:28.669 [main] info com.zhiyis.framework.learn.sort.testsort - 归并排序 time:24ms 15:35:28.696 [main] info com.zhiyis.framework.learn.sort.testsort - java.util排序 time:27ms
15:34:48.389 [main] info com.zhiyis.framework.learn.sort.testsort - 冒泡排序 time:2727ms 15:34:48.403 [main] info com.zhiyis.framework.learn.sort.testsort - 快速排序 time:18ms 15:34:48.418 [main] info com.zhiyis.framework.learn.sort.testsort - 归并排序 time:15ms 15:34:48.428 [main] info com.zhiyis.framework.learn.sort.testsort - java.util排序 time:10ms
15:33:52.156 [main] info com.zhiyis.framework.learn.sort.testsort - 冒泡排序 time:22ms 15:33:52.167 [main] info com.zhiyis.framework.learn.sort.testsort - 快速排序 time:21ms 15:33:52.171 [main] info com.zhiyis.framework.learn.sort.testsort - 归并排序 time:4ms 15:33:52.183 [main] info com.zhiyis.framework.learn.sort.testsort - java.util排序 time:12ms
15:33:34.345 [main] info com.zhiyis.framework.learn.sort.testsort - 冒泡排序 time:3ms 15:33:34.356 [main] info com.zhiyis.framework.learn.sort.testsort - 快速排序 time:17ms 15:33:34.357 [main] info com.zhiyis.framework.learn.sort.testsort - 归并排序 time:1ms 15:33:34.357 [main] info com.zhiyis.framework.learn.sort.testsort - java.util排序 time:0ms
15:33:07.920 [main] info com.zhiyis.framework.learn.sort.testsort - 冒泡排序 time:0ms 15:33:07.933 [main] info com.zhiyis.framework.learn.sort.testsort - 快速排序 time:21ms 15:33:07.933 [main] info com.zhiyis.framework.learn.sort.testsort - 归并排序 time:0ms 15:33:07.934 [main] info com.zhiyis.framework.learn.sort.testsort - java.util排序 time:1ms
如对本文有疑问, 点击进行留言回复!!
网友评论