java实现归并排序（详解）

article/2025/11/7 3:16:23

主要思想

归并排序和快速排序都是基于分而治之的算法思想。

归并排序先将待排序的数组不断拆分，直到拆分到区间里只剩下一个元素的时候。不能再拆分的时候。这个时候我们再想办法合并两个有序的数组，得到长度更长的有序数组。当前合并好的有序数组为下一轮得到更长的有序数组做好了准备。一层一层的合并回去，直到整个数组有序。
在这里插入图片描述

在这各整个过程当中，不停做的事情就是拆分问题和组合子问题的解，在这里很显然我们是需要使用递归来实现归并排序。

如何合并两个有序数组

在这里我们是一个一个的选出来的。

先选出两个数组里最小的元素，然后再选出两个数组中第二小的元素，因为两个数组都是有序的，所以两个数组里的最小的元素肯定是出现在两个数组的开头。
所以我们只需要比较两个数组中开头的两个元素，较小的那一个就是两个数组中最小的那一个，我们就将它拿出来放到一个新的地方，接着选出两个元素中第二小的元素，依然是比较这个时候两个数组开头的两个元素，谁较小，谁就是数组中第二小的，依次向下进行。
直到将所有的元素选择出来，我们就把两个有序的数组成功合并为一个更长的有序数组。

在我们实际应用的时候，两个有序数组是两个紧挨着的两个有序空间。

在使用的时候，我们先把原始数组要合并的部分复制到一个新的区域，然后在复制出来的辅助数组上设置两个下标 i 和 j ，分别指向两个有序区间的第一个元素，然后再在输入数组上设置一个变量k用于赋值。
首先比较 i 和 j 所指向的元素，我把就把小的数赋值为k，然后向后移动下标。
在这里插入图片描述

这也是个典型的空间换时间的一种做法。

在开始时那为了演示，使用的是同时拆分同时合并的，但在归并排序当中，实际使用的是按照深度优先的顺序完成归并排序的。
在这里插入图片描述

按照深度优先的顺序进行：
0 ~ 7分为0 ~ 3和4 ~ 7两组；
然后0 ~ 3分为0 ~ 1和2 ~ 3两组；
然后0 ~ 1分为 0和1；
再然后0和1整理为有序数组；
再又对2 ~ 3分为 2 和 3；
对2 和3 进行整理为有序数组；
再将 0 ~ 1和2 ~ 3进行整理为有序数组；
再对 4 ~ 7分为 4 ~ 5和 6 ~ 7两组；
。。。。。
最后整理成为有序数组。

深度优先遍历只要可以继续拆分问题，就先拆分问题；直到只有一个元素时不能拆分的时候，才回到之前它走过的地方走另一条还没有走过的路径继续走下去。直到走完所有的可能走的路径。因此称为深度优先遍历

代码实现：

import java.util.Arrays;public class Demo912_2 {public static void main(String[] args) {int[] nums = {-1, 2, -8, -10};          //给定一个数组int[] after = sortArray(nums);       //的带排序后的数组System.out.println(Arrays.toString(after)); //打印输出得到数组}private static int[] sortArray(int[] nums) {int len = nums.length;int[] temp = new int[len];mergeSort(nums,0,len-1,temp);return nums;}/*** 递归函数对nums[left...right]进行归并排序* @param nums 原数组* @param left 左边的索引* @param right 右边记录索引位置* @param temp*/private static void mergeSort(int[] nums, int left, int right, int[] temp) {if (left == right){//当拆分到数组当中只要一个值的时候，结束递归return;}int mid = (left+right)/2;   //找到下次要拆分的中间值mergeSort(nums,left,mid,temp);//记录树左边的mergeSort(nums,mid+1,right,temp);//记录树右边的//合并两个区间for (int i = left; i <= right; i++) {temp[i] = nums[i]; 
//temp就是辅助列表，新列表的需要排序的值就是从辅助列表中拿到的}int i = left;       //给辅助数组里面的值标点int j = mid +1;for (int k = left; k <= right ; k++) {//k 就为当前要插入的位置if (i == mid + 1){nums[k] = temp[j];j++;}else if (j == right+1){nums[k] = temp[i];i++;}else if (temp[i] <= temp[j]){nums[k] = temp[i];i++;}else {nums[k] = temp[j];j++;}}}
}

时间复杂度：
在这里插入图片描述

对于复杂度分析来讲，可以忽略这个常数项，而且对数的底我们也不在乎。
所以我们最终的时间复杂度为：
在这里插入图片描述

归并排序的优化

第一个优化：
可以在小区间内使用插入排序。就是在判断当left == right这里使用一个区间的插入排序，当数组长度较小的时候，使用插入排序。

在这里我们将这个值设置为16。当数组的长度小于16的时候，就使用插入排序，提高代码执行效率。
在这里插入图片描述

在这里插入图片描述

第二个优化：
就是在合并两个有序的数组之前，我们先看看这两个数组拼接起来，是不是已经成为了有序的数组。
在这里插入图片描述

最终代码：

归并排序后两种优化结束后的最终代码：

import java.util.Arrays;public class Demo912_2 {public static void main(String[] args) {int[] nums = {-1, 2, -8, -10};          //给定一个数组int[] after = sortArray(nums);       //的带排序后的数组System.out.println(Arrays.toString(after)); //打印输出得到数组}private static int[] sortArray(int[] nums) {int len = nums.length;int[] temp = new int[len];mergeSort(nums, 0, len - 1, temp);return nums;}/*** 递归函数对nums[left...right]进行归并排序** @param nums  原数组* @param left  左边的索引* @param right 右边记录索引位置* @param temp*/private static void mergeSort(int[] nums, int left, int right, int[] temp) {if (right - left < 16) {//当拆分到数组长度小于16的时候，直接插入排序来提高代码运行速度insertionSort(nums, right, left);return;}int mid = (left + right) / 2;   //找到下次要拆分的中间值mergeSort(nums, left, mid, temp);//记录树左边的mergeSort(nums, mid + 1, right, temp);//记录树右边的if (nums[mid] <= nums[mid + 1]) {//因为整数除法是向下取整，所以这里不会代写mid + 1越界return;}//合并两个区间for (int i = left; i <= right; i++) {temp[i] = nums[i]; //temp就是辅助列表，新列表的需要排序的值就是从辅助列表中拿到的}int i = left;       //给辅助数组里面的值标点int j = mid + 1;for (int k = left; k <= right; k++) {//k 就为当前要插入的位置if (i == mid + 1) {nums[k] = temp[j];j++;} else if (j == right + 1) {nums[k] = temp[i];i++;} else if (temp[i] <= temp[j]) {nums[k] = temp[i];i++;} else {nums[k] = temp[j];j++;}}}/*** 执行插入排序* @param nums* @param right* @param left*/private static void insertionSort(int[] nums, int right, int left) {for (int i = left + 1; i <= right; i++) {int temp = nums[i];int j;for (j = i; j > left; j--) {if (nums[j - 1] > temp) {nums[j] = nums[j - 1];} else {break;}}nums[j] = temp;}}
}

总结

归并排序采用的是分治算法。

分治算法每一次执行都可以分为三个步骤：

  1. 分解：把一个大问题拆成小问题；
  2. 解决：逐个解决小问题；
  3. 合并：再把这些小问题的结果组合起来组成大问题的解。

O(N logN)比O(N^2)快多少？
一段代码演示：

public class Demo {public static void main(String[] args) {for (int N = 1; N <= 100_0000; N *= 10) {System.out.printf("N = % 8d", N);System.out.printf("\t N^2 = % 14d", N*N);System.out.printf("\t NlogN = % 10f", N * Math.log(N));System.out.println();}}
}

在这里插入图片描述

我们这采用的是递归来实现归并排序，还有自底向上的归并排序和原地完成的归并排序。

在理论自底向上的归并排序是比采用递归快一丢丢的，但是考虑到学习成本来讲，就没必要了╰(●’◡’●)╮ ٩(๑′0`๑)۶

在上面的代码中，我们使用了 int mid = (left + right) / 2;来找出当前数组中的中间值.
在这里我们可以采用一个防止整型溢出的写法：
int mid = left +（right - left）/ 2;
也可以使用一个无符号右移的方式，理论上更快一点点：
int mid = left + （right - left） >> 1;
也可以直接写成：
int mid =（right - left） >> 1;
因为即使left +right会造成溢出，但右移以后，无符号的高位依然会补0，所以结论依然正确。

练习：
剑指offer 51. 数组中的逆序对
LeetCode315、计算右侧小于当前元素的个数


http://chatgpt.dhexx.cn/article/LxDYnX3W.shtml

相关文章

Launcher3--抽屉

Launcher3--抽屉

抽屉是用来放置安卓手机中所有需要显示到Launcher上的(当然也可以进行过滤&#xff0c;将不想显示的隐藏起来)应用和小部件&#xff0c;启动应用、添加快捷方式到桌面、卸载等。之前也提到过&#xff0c;有些Launcher是没有抽屉的&#xff0c;如MIUI的Launcher。在Launcher3中&…
阅读更多...
Android launcher3 开发初始篇

Android launcher3 开发初始篇

版本&#xff1a;1.0 日期&#xff1a;2014.8.26 2014.8.27 2014.11.10 版权&#xff1a;© 2014 kince 转载注明出处 好久没有写博客&#xff0c;也是因为工作比较忙的关系。当然这不是理由&#xff0c;主要是很多bug要改&#xff0c;而自己的效率又不是很高&#xff0c;…
阅读更多...
安卓Launcher 简介

安卓Launcher 简介

转载请注明出处&#xff1a;安卓Launcher 简介_安卓launcher是什么_Mr_Leixiansheng的博客-CSDN博客 文章概述&#xff1a; 1.什么是Launcher 2.新建一个Launcher工程 3.Apps去哪了 4.显示桌面背景 最近换了新工作(๑ㅁ)&#xff0c;又是要去接触新的知识了。闲话不多说&…
阅读更多...
android12.0(S) Launcher3 细节修改

android12.0(S) Launcher3 细节修改

去除 Launcher3 底部类似 dockbar 条目 packages/apps/Launcher3/src/com/android/launcher3/DeviceProfile.java availableHeightPx windowBounds.availableSize.y;mInfo info; - isTablet info.isTablet(windowBounds);//isTablet info.isTablet(windowBounds);is…
阅读更多...
Launcher3

Launcher3

Android 4.4 (KK)开始Launcher默认使用Launcher3&#xff0c;Launcher3较Launcher2 UI 有部分调整&#xff0c;主要包括: &#xff08;1&#xff09; 状态栏透明&#xff0c;App List 透Wallpaper&#xff1b; &#xff08;2&#xff09; 增加overview模式&#xff0c;可以调整…
阅读更多...
Launcher3 模块的简单设计

Launcher3 模块的简单设计

Launcher3 模块的简单设计 Lancher3 路劲&#xff1a; Z:\xxx\packages\apps\Launcher3 任务 1、AllApps背景透明化。 2、Allapps前3个图标变为Chrome、youtube、play商店。 3、长按桌面空白处在弹出的按钮下添加一个图标变大按钮&#xff0c;一个图标变小按钮&#xff0c;点…
阅读更多...
android12.0(S) Launcher3 导入 AndroidStudio 调试编译

android12.0(S) Launcher3 导入 AndroidStudio 调试编译

验证环境 aosp 12.0 源码&#xff0c;分支 android-12.0.0_r3 可以参考之前写的 android12.0(S) Pixel 3XL (QCOM 845) 编译刷机 AndroidStudio 版本 Android Studio Arctic Fox | 2020.3.1 Patch 4 gradle 版本 gradle-7.0.2-bin.zip gradle:7.0.4 二手 Pixel 3 XL一台可直…
阅读更多...
launcher3的具体学习

launcher3的具体学习

目录结构&#xff1a; allapps 目录&#xff1a;主要存放主菜单界面相关代码。 anim目录&#xff1a;存放动画相关&#xff0c; badge目录&#xff1a;存放图标标识相关 compat目录&#xff1a;存放解决兼容性相关。 config目录&#xff1a;配置Launcher相关功能的宏开关 dragn…
阅读更多...
Android10/11 原生Launcher3深度定制开发

Android10/11 原生Launcher3深度定制开发

一、引言 关于Android10和11系统Launcher3的定制有很多&#xff0c;根据项目的需求会进行各种定制开发&#xff0c; 于是就需要研究Launcher3的源码。本文主要从Android 11的Launcher3QuickStep着手 &#xff08;go版本或者其他版本类似&#xff09;从常用的修改进行分析&#…
阅读更多...
Launcher3-桌面布局+主要的类+启动流程

Launcher3-桌面布局+主要的类+启动流程

一、launhcer3桌面布局二、launcher3主要的类LauncherModel&#xff1a;BubblTextView&#xff1a;DragController&#xff1a;LauncherAppState&#xff1a;DragView&#xff1a;DragSource&#xff0c;DropTarget&#xff1a;Folder&#xff1a;FolderIcon&#xff1a;Launch…
阅读更多...
Launcher3--初识Launcher3

Launcher3--初识Launcher3

一、Launcher简介 Launcher时开机完成后第一个启动的应用&#xff0c;用来展示应用列表和快捷方式、小部件等。Launcher作为第一个(开机后第一个启动的应用)展示给用户的应用程序&#xff0c;其设计的好坏影响到用户的体验&#xff0c;甚至影响用户购机的判断。所以很多品牌厂商…
阅读更多...
Android Launcher3分析及定制主题实现

Android Launcher3分析及定制主题实现

一. Launcher3 简介 **launcher3是在Launcher2的基础上进化的版本,从Android 4.4 开始就使用Launcher3 .(kk版,kk2版)作为桌面使用,以前我们都在使用Launcher2,我们使用的是KK版本,具体区别后面再说. ** 1 Launcher3 桌面变成了动态管理,launcher2 里面默认最多加载五个worksp…
阅读更多...
Android Launcher3简介

Android Launcher3简介

一.Launcher3概述 Launcher顾名思义&#xff0c;就是桌面的意思&#xff0c;也是android系统启动后第一个启动的应用程序&#xff0c;这里以android11为例&#xff0c;和其他应用并无区别&#xff0c;只是增加了对其他app和widget的管理窗口&#xff0c;且可以为用户定制化一些…
阅读更多...
详细理解准确率、精准率、召回率，F1值等评价指标的含义

详细理解准确率、精准率、召回率，F1值等评价指标的含义

转载文章 原博客地址&#xff1a;详解准确率、精确率、召回率、F1值等评价指标的含义 机器学习问题之中&#xff0c;通常需要建立模型来解决具体问题&#xff0c;但对于模型的好坏&#xff0c;也就是模型的泛化能力&#xff0c;如何进行评估&#xff1f;我们可以定一些评价指标…
阅读更多...
详解准确率、精确率、召回率、F1值等评价指标的含义

详解准确率、精确率、召回率、F1值等评价指标的含义

机器学习问题之中&#xff0c;通常需要建立模型来解决具体问题&#xff0c;但对于模型的好坏&#xff0c;也就是模型的泛化能力&#xff0c;如何进行评估呢&#xff1f; 很简单&#xff0c;我们可以定一些评价指标&#xff0c;来度量模型的优劣。比如准确率、精确率、召回率、…
阅读更多...
分类性能评价指标——精确率，召回率，F1值详细解释

分类性能评价指标——精确率，召回率，F1值详细解释

分类性能的评价指标 准确率 准确率是全部参与分类的文本中&#xff0c;与人工分类结果吻合的文本所占的比例。 即&#xff1a;预测与真实标签相同的比例 A c c u r a c y T P T N T P T N F P F N Accuracy\frac{TPTN}{TPTNFPFN} AccuracyTPTNFPFNTPTN​ 精确率 也称…
阅读更多...
准确率、精确率、召回率、F1值

准确率、精确率、召回率、F1值

1.TP、TN、FP、FN 先粘一个官方形式的。 用新冠来举例理解。下方正方形为样本&#xff0c;其中 圆的部分认定为检测后是阳性的&#xff0c;其余部分为检测为阴性的&#xff08;但是现在的情况是检测并不完全准确&#xff0c;有可能检测时阴性&#xff0c;但实际上已经有新冠…
阅读更多...
机器学习中的二分类问题评价指标之精确率、召回率、F1值通俗理解

机器学习中的二分类问题评价指标之精确率、召回率、F1值通俗理解

引言&#xff1a;对于分类问题&#xff0c;我们在评估一个模型的好坏时&#xff0c;通常想到的是把该模型在测试集上分类结果正确的样本数量比上测试集的样本数量的比值结果&#xff0c;即准确率&#xff08;精确率&#xff09;作为评价准则。但除此之外&#xff0c;还有精确率…
阅读更多...
【转】一些因素对F1值的影响

【转】一些因素对F1值的影响

截自&#xff1a;https://blog.csdn.net/qq_27590277/article/details/88374695 https://blog.csdn.net/qq_27590277/article/details/88367082 一些因素对F1值的影响 如果还没了解F1值的话&#xff0c;这里有我之前写的通俗易懂的文章 详谈P(查准率)&#xff0c;R(查全率)&…
阅读更多...
keras计算precision、recall、F1值

keras计算precision、recall、F1值

近期写课程作业&#xff0c;需要用Keras搭建网络层&#xff0c;跑实验时需要计算precision&#xff0c;recall和F1值&#xff0c;在前几年&#xff0c;Keras没有更新时&#xff0c;我用的代码是直接取训练期间的预测标签&#xff0c;然后和真实标签之间计算求解&#xff0c;代码…
阅读更多...
推荐文章

Copyright @ 2022~2023