冒泡、归并和快速的算法试验
程序员文章站
2022-06-22 12:54:57
1. 冒泡、归并和快速的算法试验 1.1. 冒泡排序 / 冒泡排序 / private void bubbleSort(int[] arr) { for (int i = arr.length; i 0; i ) { for (int j = arr.length 1; j arr.length i ......
1. 冒泡、归并和快速的算法试验
1.1. 冒泡排序
/** * 冒泡排序 */ 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; } } } }
1.2. 快速排序
/** * 快速排序 */ 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); }
1.3. 归并排序
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); }
1.4. 测试代码
@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)); }
1.5. 测试结果
- 当数组长度60000时
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
- 当数组长度30000时
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
- 当数组长度3000时
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
- 当数组长度300时
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
- 当数组长度30时
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
1.6. 总结
- 我的测试有什么变量控制问题可以提出来
- 冒泡排序的时间复杂度最好是o(n),平均和最差o(n^2);快速排序最好nlog_2 n,平均也是nlog_2 n,最差n^2;归并排序最好平均和最差都是nlog_2 n。根据算法时间复杂度看,归并排序最稳定
- 根据实验结果看,在排序数量比较少的情况下冒泡排序效率也还可以,但一旦排序数量多了,还是快速和归并效率较高。当然我们往往就用java默认提供给我们的工具类就可以了,不用自己写算法,效率不比归并差。
上一篇: 20190227-做一个简易代码统计工具
下一篇: HTML知识点总结之table
推荐阅读
-
Python实现的插入排序,冒泡排序,快速排序,选择排序算法示例
-
java 合并排序算法、冒泡排序算法、选择排序算法、插入排序算法、快速排序算法的描述
-
Python实现的插入排序,冒泡排序,快速排序,选择排序算法示例
-
【PHP面试题】通俗易懂的两个面试必问的排序算法讲解:冒泡排序和快速排序
-
JS实现的冒泡排序,快速排序,插入排序算法示例
-
冒泡、归并和快速的算法试验
-
浅谈PHP第二弹---经典算法的运用(冒泡排序和快速排序)
-
浅谈PHP第二弹---经典算法的运用(冒泡排序和快速排序)_PHP教程
-
php的一些简单算法程序(冒泡、快速等),php算法程序冒泡_PHP教程
-
php的一些容易算法程序(冒泡、快速等)