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

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

在学C++的时候，也学了两数交换：《小朋友学C++（14）：两数交换》
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函数是由<algorithm>提供的。可见自己写的两个函数，一定存在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

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

加入少儿信息学奥赛QQ群请扫左侧二维码，关注微信公众号请扫右侧二维码

QQ群和公众号.png