Java 中的自上而下/自下而上的合并排序
2022/11/20 1:23:58
本文主要是介绍Java 中的自上而下/自下而上的合并排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
定时实验结果预测
自下而上的方法应该表现得更好:
-
自上而下的方法递归调用,这将占用 O(logN) 额外的函数调用堆栈空间
mergeSortHelper
-
自上而下的方法需要 O(logN) 额外的时间将数组分解为一个/零个元素
但是它们的空间复杂性都是O(N)(存储排序数据的临时数组)
定时实验结果
自下而上的方法有时比自上而下的方法略好
趋势表明,两种方法的性能之间没有太大差异。
关于为什么两种方法之间的差距不是那么明显的一些个人猜测:
- 我选择的数据点不是最好的演示文稿
- 我的实现不是最佳实践
- 该部分花费了太多时间,以至于它掩盖了故障过程/额外的调用堆栈空间
merge
- 编译器在引擎盖下做了一些优化黑魔法
关于测试:
- 测试数据集:随机排列整数数组列表
- 测试数据类型:整数
- 测试数据大小:[0, 10k],步长:500
- 每个数据点的跟踪数:10000
自上而下/递归合并排序
/** * @return integer overflow prevention mid index getter */ private static int getMiddleIndex(int start, int end) { return start + (end - start) / 2; } /** * merge two sorted array into a new sorted array */ private static <T> void merge(ArrayList<T> data, int startLeft, int endLeft, int startRight, int endRight, Comparator<? super T> comparator, ArrayList<T> sortedResults) { int leftPointer = startLeft, rightPointer = startRight; int index = startLeft; while (leftPointer <= endLeft && rightPointer <= endRight) { T data1 = data.get(leftPointer); T data2 = data.get(rightPointer); if (comparator.compare(data1, data2) < 0) { sortedResults.set(index, data1); leftPointer++; } else { sortedResults.set(index, data2); rightPointer++; } index++; } while (leftPointer <= endLeft) { sortedResults.set(index, data.get(leftPointer)); leftPointer++; index++; } while (rightPointer <= endRight) { sortedResults.set(index, data.get(rightPointer)); rightPointer++; index++; } for (int i = startLeft; i <= endRight; i++) { data.set(i, sortedResults.get(i)); } } /** * merge sort, time complexity: O(N*logN), space complexity: O(N) */ private static <T> void mergeSortHelper(ArrayList<T> data, int start, int end, Comparator<? super T> comparator, ArrayList<T> sortedResults) { int dataSize = end - start + 1; if (dataSize < 2) { return; } int mid = getMiddleIndex(start, end); mergeSortHelper(data, start, mid, comparator, sortedResults); mergeSortHelper(data, mid + 1, end, comparator, sortedResults); merge(data, start, mid, mid + 1, end, comparator, sortedResults); } /** * call mergeSortHelper to do top down merge sort */ public static <T> void topDownMergeSort(ArrayList<T> data, Comparator<? super T> comparator) { ArrayList<T> sortedResults = new ArrayList<>(Collections.nCopies(data.size(), null)); mergeSortHelper(data, 0, data.size() - 1, comparator, sortedResults); }
自下而上/迭代合并排序
public static <T> void bottomUpMergeSort(ArrayList<T> originalData, Comparator<? super T> comparator) { ArrayList<T> sortedResults = new ArrayList<>(Collections.nCopies(originalData.size(), null)); for (int sortingRange = 1; sortingRange < originalData.size(); sortingRange *= 2) { for (int left = 0; left < originalData.size(); left += 2 * sortingRange) { bottomUpMerge(originalData, sortedResults, left, sortingRange, comparator); } copyArray(sortedResults, originalData); } } private static <T> void bottomUpMerge(ArrayList<T> originalData, ArrayList<T> sortedResults, int start, int sortingRange, Comparator<? super T> comparator) { int right = Math.min(start + sortingRange, originalData.size()); int end = Math.min(start + 2 * sortingRange, originalData.size()); int leftPointer = start; int rightPointer = leftPointer + sortingRange; int index = start; while (leftPointer < right && rightPointer < end) { if (comparator.compare(originalData.get(leftPointer), originalData.get(rightPointer)) <= 0) { sortedResults.set(index, originalData.get(leftPointer)); leftPointer++; } else { sortedResults.set(index, originalData.get(rightPointer)); rightPointer++; } index++; } while (leftPointer < right) { sortedResults.set(index, originalData.get(leftPointer)); leftPointer++; index++; } while (rightPointer < end) { sortedResults.set(index, originalData.get(rightPointer)); rightPointer++; index++; } } /** * copy everything in the "from" array into "to" array */ private static <T> void copyArray(ArrayList<T> from, ArrayList<T> to) { if (from.size() != to.size()) { throw new UnsupportedOperationException("From & to arrays have different sizes!"); } for (int i = 0; i < from.size(); i++) { to.set(i, from.get(i)); }
标签:java,函数,学习,系统,语言,平台,方法,安装, 来源:
本站声明: 1. iCode9 技术分享网(下文简称本站)提供的所有内容,仅供技术学习、探讨和分享; 2. 关于本站的所有留言、评论、转载及引用,纯属内容发起人的个人观点,与本站观点和立场无关; 3. 关于本站的所有言论和文字,纯属内容发起人的个人观点,与本站观点和立场无关; 4. 本站文章均是网友提供,不完全保证技术分享内容的完整性、准确性、时效性、风险性和版权归属;如您发现该文章侵犯了您的权益,可联系我们第一时间进行删除; 5. 本站为非盈利性的个人网站,所有内容不会用来进行牟利,也不会利用任何形式的广告来间接获益,纯粹是为了广大技术爱好者提供技术内容和技术思想的分享性交流网站。
这篇关于Java 中的自上而下/自下而上的合并排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-13怎么通过 JavaScript 或其他编程语言来实现监听屏幕高度变化功能?-icode9专业技术文章分享
- 2024-11-12聊聊我们那些年用过的表达式引擎组件
- 2024-11-12让项目数据更有说服力:五款必备数据可视化管理工具推荐
- 2024-11-12人到一定年纪,要学会远离多巴胺
- 2024-11-12解读:精益生产管理的目的是什么?如何操作?
- 2024-11-12Sku预研作业
- 2024-11-12文心一言API密钥:分步申请指南
- 2024-11-12初学者指南:轻松掌握后台交互
- 2024-11-12从零开始学习:封装基础知识详解
- 2024-11-12JSON对象入门教程:轻松掌握基础用法