小朋友学经典算法（13）：两数交换

妖狐艹你老母 2022-05-16 10:21 139阅读 0赞

在学C语言的时候，学过两数交换：《小朋友学C语言（25）：两数交换》  
[https://www.jianshu.com/p/64bc70f0abfe][https_www.jianshu.com_p_64bc70f0abfe]

在学C++的时候，也学了两数交换：《小朋友学C++（14）：两数交换》  
[https://www.jianshu.com/p/9a071870e0a0][https_www.jianshu.com_p_9a071870e0a0]

这里咱们要考虑的是，两个数相等的交换情况。

#include <iostream>
    #include <algorithm>
    using namespace std;
    
    // 两个参数是指针（指向地址的引用）
    void myswap(int *x, int *y)
    {
        *x ^= *y;
        *y ^= *x;
        *x ^= *y;
    }
    
    // 两个参数是引用，在这里&代表引用，不代表地址
    void myswap2(int &x, int &y)
    {
        x ^= y;
        y ^= x;
        x ^= y;
    }
    
    int main()
    {
        cout << "**********交换不同的值**********" << endl;
        int a = 1, b = 2;
        myswap(&a, &b); // 因为myswap的参数是指针，所以必须传地址
        cout << a << ' ' << b << endl;
    
        int a2 = 3, b2 = 4;
        myswap2(a2, b2);
        cout << a2 << ' ' << b2 << endl;
    
        cout << "**********交换相同的值**********" << endl;
        int a3 = 5, b3 = 5;
        myswap(&a3, &b3); // 因为myswap的参数是指针，所以必须传地址
        cout << a3 << ' ' << b3 << endl;
    
        int a4 = 6, b4 = 6;
        myswap2(a4, b4);
        cout << a4 << ' ' << b4 << endl;
    
        int c[1];
        c[0] = 7;
        myswap(&c[0], &c[0]);
        cout << c[0] << ' ' << c[0] << endl;
    
        int d[1];
        d[0] = 8;
        myswap2(d[0], d[0]);
        cout <<d[0] << ' ' << d[0] << endl;
    
        int e[1];
        e[0] = 9;
        swap(e[0], e[0]);
        cout <<e[0] << ' ' << e[0] << endl;
    
        return 0;
    }

运行结果：

**********交换不同的值**********
    2 1
    4 3
    **********交换相同的值**********
    5 5
    6 6
    0 0
    0 0
    9 9

结果显示，前两组数值不同的两个数，能交换成功。后五组相同的值，交换成功的有3组。不成功的有两组，并且值都变成了0。  
这是什么原因呢？  
观察最后三对的数，都是数组里的同一元素交换。myswap和myswap2函数是咱们自己定义的，swap函数是由提供的。可见自己写的两个函数，一定存在bug。

仔细观察，发现a3 = 5, b3 = 5，这是两个不同的变量（在内存里的地址不同），而myswap2(d\[0\], d\[0\])，这是对同一个地址里的数交换。  
d0 = 8时，  
a = a ^ b = 8 ^ 8 = 0，因为a和b都指向d0，所以此时b = a = 0。  
b = b ^ a = 0 ^ 0 = 0，  
a = a ^ b = 0 ^ 0 = 0，  
所以最终得到的是0 0，而不是8 8。  
对于myswap(&c\[0\], &c\[0\])，与myswap2(d\[0\], d\[0\])的道理是一样的。

改进：如果值一样，那就不用交换了：

#include <iostream>
    #include <algorithm>
    using namespace std;
    
    // 两个参数是指针（指向地址的引用）
    void myswap(int *x, int *y)
    {
        if(x != y)
        {
            *x ^= *y;
            *y ^= *x;
            *x ^= *y;
        }
    }
    
    // 两个参数是引用，在这里&代表引用，不代表地址
    void myswap2(int &x, int &y)
    {
        if(x != y)
        {
            x ^= y;
            y ^= x;
            x ^= y;
        }
    }
    
    int main()
    {
        cout << "**********交换不同的值**********" << endl;
        int a = 1, b = 2;
        myswap(&a, &b); // 因为myswap的参数是指针，所以必须传地址
        cout << a << ' ' << b << endl;
    
        int a2 = 3, b2 = 4;
        myswap2(a2, b2);
        cout << a2 << ' ' << b2 << endl;
    
        cout << "**********交换相同的值**********" << endl;
        int a3 = 5, b3 = 5;
        myswap(&a3, &b3); // 因为myswap的参数是指针，所以必须传地址
        cout << a3 << ' ' << b3 << endl;
    
        int a4 = 6, b4 = 6;
        myswap2(a4, b4);
        cout << a4 << ' ' << b4 << endl;
    
        int c[1];
        c[0] = 7;
        myswap(&c[0], &c[0]);
        cout << c[0] << ' ' << c[0] << endl;
    
        int d[1];
        d[0] = 8;
        myswap2(d[0], d[0]);
        cout <<d[0] << ' ' << d[0] << endl;
    
        int e[1];
        e[0] = 9;
        swap(e[0], e[0]);
        cout <<e[0] << ' ' << e[0] << endl;
    
        return 0;
    }

运行结果：

**********交换不同的值**********
    2 1
    4 3
    **********交换相同的值**********
    5 5
    6 6
    7 7
    8 8
    9 9

现在结果对了。在此，咱们可以进一步推断中的swap函数的实现方式：  
（1）参数是用引用而不是用指针，因为调用方式 是swap(e\[0\], e\[0\])而不是swap(&e\[0\], &e\[0\])  
（2）swap内部用if作了判断。

> 加入少儿信息学奥赛QQ群请扫左侧二维码，关注微信公众号请扫右侧二维码  
> ![QQ群和公众号.png][QQ_.png]

[https_www.jianshu.com_p_64bc70f0abfe]: https://www.jianshu.com/p/64bc70f0abfe
[https_www.jianshu.com_p_9a071870e0a0]: https://www.jianshu.com/p/9a071870e0a0
[QQ_.png]: /images/20220516/746c44b699fd4da0b24cbe35eaeb3538.png