分类： C/C++
2015-05-25 14:33:51
原文地址：花样swap函数 作者：dream_my_dream
其中swap的函数原型为：
（1）void swap (int &a,int &b);传引用
（2）void swap(int *a,int *b);传地址
Swap函数常见的几种写法：
（1）使用临时变量
void swap(int *a,int *b)
{
int t;
t=*a;
*a=*b;
*b=t;
}
（2）使用加减法计算
void swap1(int *a,int *b)
{
*a=*a+*b;
*b=*a-*b; //*b=*a+*b-*b=*a
*a=*a-*b; //*a=*a+*b-*a=*b
}
（3）使用乘除法计算
void swap2(int *a,int *b)
{
*a = (*a)*(*b) ;
*b = (*a) / (*b);
*a = (*a) / (*b) ;
}
（4）使用异或位运算
void swap3(int *a,int *b)
{
*a = *a^*b;
*b = *a^*b;
*a = *a^*b;
//a ^= b ^=a ^= b; ¨精简写法
}
二进制异或运算的规则：相同为0，相异为1
对任意数 A ，B ，C
（1）A ^ 0 = A
（2）A ^ A = 0
（3）(A ^B)^C=A^(B^C)
（4）A^B = B^A
我们看到函数swap3（）中，我们姑且将这两个参数成为a,b
第一句 a = a^b; 让 c =a^b;
第二句 b = a^b;其时就是 b = c^b =a^(b^b)=a^0=a;
第三句 a = a^b;其时就是 a = c^b =a^b^a=b^(a^a)=b^0=b;
性能分析：
（1）空间性能
空间性能上swap（）浪费一个int 空间，其他没有空间开销。
（2）时间性能
时间性能上，虽然说都是执行3条语句，但是与语句不一样，效率上 ：位运算>加减>乘除 。大致上是这样，当然具体情况还得具体分析。
稳定性：
Swap2，swap3，参数是int型，进行算术运算容易出现溢出。经过测试发现，虽然会产生溢出，但仍可以交换成功。对于乘除法运算的交换函数，若其中的一个数为0时，会出现什么情况呢?不同的编译器在此时会有不同的响应，在GCC下会提示段错误，codeblocks下会提示*.exe停止工作。
以加法运算的交换函数为例：
A与b相加后，显然已经超出int的范围了，运行结果如下：
相对而言，swap4使用位运算就好多了。然而，难有十全十美的事啊，如果相同的两个数进行交换，那么结果会如何呢？
Swap的其他写法：
（1）经典型改进版---范型法
原型：void* memcpy(void *dest,void *src,unsigned int n)
作用：由src所指内存区域复制n个字节到dest所指内存区域。
说明：src和dest所指内存区域不能重叠，函数返回指向dest的指针。
void Swap4(void* vp1, void* vp2, int size)
{
void* p = (void*)malloc(size);
assert(p != NULL);
memcpy(p, vp1, size);
memcpy(vp1, vp2, size);
memcpy(vp2, p, size);
free(p);
}
该函数的形参不再是指向某一个特定对象的指针，而是指向void对象的指针，我们是要交换vp1和vp2所指向的内容，那么该函数却不知道该内容的具体大小，因为我们只传入了这两个内存块的地址，所以增加了第三个形参size，该形参表明了所要交换的内存块的大小。这样在实现的过程中只要动态申请一个空间，然后在调用内存拷贝函数memcpy就行了，只是不要忘了free申请的空间。
（2）模仿memcpy实现swap
void swap5(void *a,void *b,size_t size)
{
unsigned char *p1=(unsigned char *)a; //强制类型转换
unsigned char *p2=(unsigned char *)b;
unsigned char temp; //临时的字节型变量
while(size--)
{
temp=*p1;
*p1=*p2;
*p2=temp;
p1++;
p2++;
}
}
使用的时候可以这样调用：swap( &a,&b,sizeof(int) );
这种字节的分别交换可以通用各种类型的交换，当然，彼此之间应该是同种类型，否则会因为类型大小，字节序等一些问题发生错误。
（3）使用双重指针
void swap6(int **x, int **y)
{
int *temp;
temp=*x;
*x=*y;
*y=temp;
}
