【排序算法】归并排序
2023-04-18 15:33:28 时间
1 前言
今天把排序的几个算法过一下,这节我们看一下归并排序,简单的来说就是先拆再合,跟快排相反(快排时先找位置再两边拆),我们看示例。
2 代码示例
/** * 归并排序 * 特点就是 跟快排相反,快排是先找再拆分,归并是先拆再合 * 折半拆,指导拆分单个以后开始向上汇集 */ public static void mergeSort(int[] arr, int[] res, int start, int end) { // 递归的出口,元素只有一个的时候直接返回 if (start >= end) { return; } // 计算中间索引位置 int middle = start + (end - start) / 2; // 拆分成两半,左边就是 0 ~ middle 右边就是 middle+1 ~ end int rightStart = middle + 1; // 左侧进行递归 mergeSort(arr, res, start, middle); // 右侧进行递归 mergeSort(arr, res,rightStart, end); // 开始汇集结果 // 左侧索引变量 int leftIndex = start; // 右侧索引变量 int rightIndex = rightStart; // 结果的索引变量 int index = start; // 左右两侧的数据都未汇集结束时 while (leftIndex <= middle && rightIndex <= end) { // 升序,当左侧的值小于右侧的话,收集左侧的并将索引++ if (arr[leftIndex] < arr[rightIndex]) { res[index++] = arr[leftIndex++]; continue; } // 右侧的值小于左侧的,收集右侧的并将索引++ res[index++] = arr[rightIndex++]; } // 左侧的未处理干净时,收集剩余的 while (leftIndex <= middle) { res[index++] = arr[leftIndex++]; } // 右侧的未处理干净时,收集剩余的 while (rightIndex <= end) { res[index++] = arr[rightIndex++]; } /** * 这个是将排序后的顺序进行回写 * 为什么要回写呢?因为后一次的结果汇集依赖前一次的结果 * * 为什么要多个参数 res? * 这个我们在中间做拆分进行部分结果排序的时候不能直接在源数组上变更,所以需要个数据来存放排完序后覆盖回去 */ for (int i=start; i <= end; i++) { arr[i] = res[i]; } } public static void main(String[] args) { int[] arr = IntStream.generate(() -> ThreadLocalRandom.current().nextInt(10000)).limit(10000).toArray(); System.out.println("排序前:" + Arrays.stream(arr).mapToObj(String::valueOf).collect(Collectors.joining(","))); int[] res = new int[arr.length]; mergeSort(arr, res, 0, arr.length - 1); System.out.println("排序后:" + Arrays.stream(arr).mapToObj(String::valueOf).collect(Collectors.joining(","))); }
3 小结
有写的不对的地方,欢迎指正哈。
相关文章
- 请讨论分层,而不是三层
- 三层究竟如何?
- Visual C# 2010新特性之dynamic类型
- Asp.net MVC 示例项目"Suteki.Shop"分析之---ViewData
- 使用silverlight构建一个工作流设计器(十二)(附源代码下载、在线演示、视频教程)
- 在简单控制台程序中获取并使用参数
- 博客园北京俱乐部第三次活动杂记
- 关于程序的一些看法和简单建议
- WF4.0 Beta1之旅(2):异常处理
- C# 调用 Google Earth Com API开发(三)
- VS2010 Beta1下Silverlight3试用手记
- WF4.0 Beta1之旅(1):基本介绍
- 循证架构--寻找最适合自己的架构
- Visual Studio 2010 and .NET Framework 4 Beta 1发布
- 也谈实体验证(Entity Validation)
- 我的架构经验小结(四)-- 实战中演化的三层架构
- 使用silverlight构建一个工作流设计器(十)(附源代码下载、在线演示、视频教程)
- Silverlight 3试用手记
- Asp.net MVC 示例项目"Suteki.Shop"分析之---Controller
- Stress Managment - 压力管理