专栏首页机器学习入门算法细节系列(1):Java swap

算法细节系列(1):Java swap

算法细节系列(1):Java swap

问题

在C++中,swap算法可以用指针来实现,因此在Java中,如果采用如下代码来对两个数字进行交换时,也不会影响两个对象的值。

public class TestSwap {

    public static void main(String[] args) {
        int a =2;
        int b =3;
        System.out.println("交换前 -> "+a+":"+b);
        swap(a, b);
        System.out.println("交换后 -> "+a+":"+b);
    }

    public static void swap(int a,int b){
        int temp =a;
        a = b;
        b = temp;
    }
}

console输出结果为:

交换前 -> 2:3
交换后 -> 2:3

原因

在Java中,对基本类型的操作都是传值操作,在进入swap语句中时,我把a的值传给了新的变量a,而非原先的变量a。这在C++中,也是一个道理。但你又问了,Java不是实现了引用嘛,看如下代码

/**引用传递**/
StringBuffer sb = new StringBuffer("Hello");
addStr(sb);
System.out.println(sb);

public static void addStr(StringBuffer sb){
    sb.append(",my name is demon!");
}

console输出结果为:

Hello,my name is demon!

StringBuffer是Java中的类,定义了一个addStr()方法,并把sb对象,传入到方法中去,并且成功的改变了sb的值,这就说明进入方法体后,方法体中的局部变量sb指向了存放“Hello”的对象内存去了,不管这个指向是引用还是指针,起码引用传递能够改变原先变量sb的值嘛。

没错,但在Java中,对类有两类划分,一类为基本类型,即我们见到的int,char,byte….等等这些小写开头的基本数据类型,还有一类在Java类库中都是以class关键字定义的类型,该类型为引用类型,即只有这些以class定义的类型才能够真正实现引用传递,而基本类型传递的只是参数值而已。

于是我便突发奇想,嗯,在《Thinking in Java》中提到,每个基本类型都有对应的包装类,即Int ->Integer char -> Character,包装类都是用class定义的引用类型,于是咱们来试试对包装类的参数传递是什么结果?

Integer integerA = new Integer(2);
Integer integerB = new Integer(3);

System.out.println("交换前 -> "+integerA+":"+integerB);
swap(integerA, integerB);
System.out.println("交换前 -> "+integerA+":"+integerB);

public static void swap(Integer a,Integer b){
    Integer temp =a;
    a = b;
    b = temp;
}

console输出结果:

交换前 -> 2:3
交换前 -> 2:3

大失所望,怎么回事啊,包装类不是引用类型嘛,为何依旧无法实现swap的正确传值?思考了很久,结合自己封装的包装类是如何实现swap的,得出了比较合理的解释,其实引用本身是对一个类的别名!它不像C++中的指针那样,如果指针指向某个内存单元,对它赋值就能直接改变内存单元的值,对内存单元的操作,直接由指针指向来完成。在Java中,上述版本的swap方法,显然并没有对引用指向的内存单元进行操作,而只是改变了引用的指向。

进入swap方法体后,a = integerA,b =integerB,引用a和引用b,copy了实际变量integerA和integerB,也就是说,虽然方法体内完成了对引用的交换,但a和b分别为躺在内存中的实际数据2和3的另外一个指向罢了。方法体中完成了交换,却不影响integerA和integerB的指向。那跟基本类型的值传递有何区别,基本类型的传递是拷贝内存单元的实际数据,即内存单元中存在两份一模一样的数据,分别由变量a和方法体内的a表示,而引用传递,在内存单元中只存放了一份实际数据,只是变量integerA和方法体内的a均指向该内存单元。

而明显的,只有当方法体中的a对包装类的值进行改变时,才能够影响integerA中内存单元的值。而如果只是简单的对引用进行操作,那么即使是包装类也无法产生效果,从sb中也可以看出,它append了”my name is demon.”这就是对指向该内存单元的数据做了改变,由此改变了原先sb的值。

因此,我们得出一个解决方案,封装自己的包装类,实现引用传递,并且在引用传递的过程中,要改变实际内存单元的值。所以在包装类中我们需要有一个改变类中基本类型的方法。这也就解释了为什么Integer无法实现swap的原因了,不变类中的基本类型是final类型的,即它只允许初始化一次,后续是不能被改变的,否则就不符合int基本类型的性质,且你在Integer官方提供的方法中也无法找到改变初始值的方法。

自己实现的MyInteger实现数据交换:

public class MyInteger {

    private int num;

    public MyInteger(int num){
        this.num = num;
    }

    public int getNum() {
        return this.num;
    }

    public void setNum(int num){
        this.num = num;
    }

    @Override
    public String toString() {
        return num+"";
    }
}

/**引用传递+改变内存单元**/
MyInteger integerA = new MyInteger(2);
MyInteger integerB = new MyInteger(3);
System.out.println("交换前 -> "+integerA+":"+integerB);
swap(integerA, integerB);
System.out.println("交换前 -> "+integerA+":"+integerB);

public static void swap(MyInteger a,MyInteger b){
    MyInteger temp =new MyInteger(a.getNum());//拷贝一份新的值
    a.setNum(b.getNum());;//a为b的值
    b.setNum(temp.getNum());//b为a的值
}

console输出结果:

交换前 -> 2:3
交换前 -> 3:2

欣喜若狂,反复倒腾,总算改变了变量a和b的值。oh,my god!但自己的包装类是没法进行Java自动装箱滴,显然类的封装破坏了基本类型的约束,因此该包装是失败的,在实际过程,我们很有可能因为使用这个类导致一些看不到的bug,因此针对swap方法,我们再提出一种新的解决方案,上述解决方案只为了帮助理解引用,指针,参数传递,引用传递的概念。

正解

在很多排序算法中,它们是这么干的!

int[] data = {2,3};
System.out.println("交换前 -> "+data[0]+":"+data[1]);
swap(data, 0,1);
System.out.println("交换前 -> "+data[0]+":"+data[1]);

public static void swap(int[] data, int a, int b) {  
    int t = data[a];  
    data[a] = data[b];  
    data[b] = t;  
} 

这可是结合了指针概念和排序算法的实际应用啊,咱们来谈谈该设计哲学,首先,大多数的排序算法的输入均为一个数组,各种基本类型的组合。因此,swap基本都用在排序算法中,而对数组的传递,实际背后原理是对指针的应用,所以该方法是奏效的。

参考资料

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 聊聊elasticsearch的RoutingService

    elasticsearch-7.0.1/server/src/main/java/org/elasticsearch/cluster/routing/Routi...

    codecraft
  • 为什么大部分码农做不了软件架构师?

    小团队一般 10 人左右,其中常常是技术最牛的人做架构师(或TL)。所以,架构师在广大码农中的占比大概平均不到 10%。而架构师也可以分为初级、中级、高级三档,...

    芋道源码
  • 突发!Java首度承认失败,愿永久服软Python!网友:好想哭!

    最近,这个格局已经被悄然打破,正是被来自曾经的小弟,新晋网红Python给硬生生拽下神坛。对此,Java曾表示强烈质疑,最近一份数据榜单悄悄来了!

    AI科技大本营
  • 阿里 P8 Java 高级工程师,都需要掌握哪些技术栈?

    大家都知道,阿里P8高级技术专家,基本上是一线技术人能达到的最高职级,也是很多程序员追求的目标。

    Java技术栈
  • leecode刷题(27)-- 合并k个排序链表

    以前做过合并两个有序链表的问题,所以刚开始想到的解法与之类似,我们可以先合并两个有序链表,再用合并的新链表去合并第三个链表:

    希希里之海
  • 史上最污技术解读,我竟然秒懂了!

    很多同学对热备,冷备,云备了解不深,我科普一下 IT 行业各种备份术语。以后别闹笑话了。

    用户1516716
  • Java高效开发12个精品库

    第一个要说的当然是JUnit了,JUnit毕竟是Java圈目前最知名及常用的测试框架。JUnit之所以能够成为Java圈中最热门的测试库,是因为对于很多项目而言...

    java思维导图
  • 80后程序员降薪6K,预感中年危机来袭,准备跳槽却碰壁

    一提及程序员,很多人想到的都是“工资高”“技术好”诸如此类的,可见程序员是个非常赚钱的职业,所以每年都会有很多毕业生来选择这个行业。

    美的让人心动
  • 为什么大部分码农做不了系统架构师?

    小团队一般 10 人左右,其中常常是技术最牛的人做架构师(或TL)。所以,架构师在广大码农中的占比大概平均不到 10%。

    Java技术栈
  • Spring Boot 注册 Servlet 的三种方法,真是太有用了!

    本文栈长教你如何在 Spring Boot 注册 Servlet、Filter、Listener。

    Java技术栈

扫码关注云+社区

领取腾讯云代金券