常见swap()函数实现和细节讲解_swap函数

前言说明

swap()函数的作用是进行交换传入的两个值。

本文都以整形int举例说明，且用C语言描述

常见的swap的实现方式有三种

• 格外一个空间的临时存放发
• 无格外空间的位运算异或法
• 无额外空间的加减法

主程序框架

#include <stdio.h>

void swap(int *a, int *b){
//    return ;
}

int main (void)
{
    int a = 3;
    int b = 4;

    swap(&a, &b);

    printf("a = %d\n", a);
    printf("b = %d\n", b);

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
'
运行
运行

格外空间法

C++中的swap()函数就是用的这个算法

void swap(int *a, int *b){
    int tmp = *a;
    *a = *b;
    *b = tmp;
}
1
2
3
4
5

位运算法（异或）

异或运算，相同为真，相异为假

void swap(int *a, int *b){
    *a = *a^*b;
    *b = *a^*b;
    *a = *a^*b;
}
1
2
3
4
5

简写法

void swap(int *a, int *b){
//    简写1
    *a ^= *b;
    *b ^= *a;
    *a ^= *b;

//    简写2
    *a ^= *b ^= *a ^= *b;
}
1
2
3
4
5
6
7
8
9

具体细节举例：

加减法

void swap(int *a, int *b)
{
    *a = *a+*b;
    *b = *a-*b;
    *a = *a-*b;
}

1
2
3
4
5
6
7

简写

void swap(int *a, int *b)
{
//    简写
    *b -= *a += *b;
    *a -= *b *= -1;
}
1
2
3
4
5
6

具体细节举例：

无额外空间的缺陷

加减法最显而易见的缺陷就是数据溢出问题。这是本身情况下绝对无法改变和避免的。

异或法 和 加减法共有缺陷，是对同一个数据，不是说单纯的两个数值相等，而是同一个数据，同时传给了swap就是swap的两个参数a,b接受到了**同一个地址**。

理论上一个元素和自身交换，那就是等于没有交换，值还是本身。但实际上最后的结果是变为0

理由见下：

因此，为了避免这种情况，我们可以在运算前进行判断

void swap(int *a, int *b)
{
    //不加*表示地址相同，避免同地址使得单个地址的元素清零
    if (a == b) return ;
    //加*表示数值相同，没必要交换
    if (*a == *b)   return ;
}
1
2
3
4
5
6
7

不常见的swap()实现方法

申请更多空间法

此法过于幼稚，仅当娱乐

void swap(int *a, int *b)
{
    int x = *a;
    int y = *b;
    *a = y;
    *b = x;
}
1
2
3
4
5
6
7

位运算类似加减效果法

此法解释起来过于复杂，仅当娱乐

void swap(int *a, int *b)
{
    *a = (*a&~*b)|(*b&~*a);
    *b = (*a&~*b)|(*b&~*a);
    *a = (*a&~*b)|(*b&~*a);
}
1
2
3
4
5
6

为什么说类似加减法效果，见图：