免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 1096 | 回复: 5

[学习分享] 花样swap函数 [复制链接]

论坛徽章:
0
发表于 2015-05-11 07:51 |显示全部楼层
本帖最后由 dream_my_dream 于 2015-05-11 07:58 编辑

                    花样Swap函数
其中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停止工作。

相对而言,swap4使用位运算就好多了。然而,难有十全十美的事啊,如果相同的两个数进行交换,那么结果会如何呢?
图片1.png
4.png

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;
   }

论坛徽章:
22
丑牛
日期:2014-08-15 14:32:0015-16赛季CBA联赛之同曦
日期:2017-12-14 15:28:14黑曼巴
日期:2017-08-10 08:14:342017金鸡报晓
日期:2017-02-08 10:39:42黑曼巴
日期:2016-11-15 15:48:38CU十四周年纪念徽章
日期:2016-11-09 13:19:1015-16赛季CBA联赛之同曦
日期:2016-04-08 18:00:03平安夜徽章
日期:2015-12-26 00:06:30程序设计版块每日发帖之星
日期:2015-12-03 06:20:002015七夕节徽章
日期:2015-08-21 11:06:17IT运维版块每日发帖之星
日期:2015-08-09 06:20:002015亚冠之吉达阿赫利
日期:2015-07-03 08:39:42
发表于 2015-05-11 09:31 |显示全部楼层
很有意义,谢谢lz

论坛徽章:
0
发表于 2015-05-14 22:47 |显示全部楼层
本帖最后由 dream_my_dream 于 2015-05-14 22:51 编辑

论坛徽章:
0
发表于 2015-05-14 22:49 |显示全部楼层
回复 2# amarant

初来乍到,多谢版主的肯定
   

论坛徽章:
22
丑牛
日期:2014-08-15 14:32:0015-16赛季CBA联赛之同曦
日期:2017-12-14 15:28:14黑曼巴
日期:2017-08-10 08:14:342017金鸡报晓
日期:2017-02-08 10:39:42黑曼巴
日期:2016-11-15 15:48:38CU十四周年纪念徽章
日期:2016-11-09 13:19:1015-16赛季CBA联赛之同曦
日期:2016-04-08 18:00:03平安夜徽章
日期:2015-12-26 00:06:30程序设计版块每日发帖之星
日期:2015-12-03 06:20:002015七夕节徽章
日期:2015-08-21 11:06:17IT运维版块每日发帖之星
日期:2015-08-09 06:20:002015亚冠之吉达阿赫利
日期:2015-07-03 08:39:42
发表于 2015-05-15 10:17 |显示全部楼层
回复 4# dream_my_dream


    多来逛逛,未来是你们的

论坛徽章:
0
发表于 2015-05-15 22:38 |显示全部楼层
回复 5# amarant

嗯嗯。的确能找到很多有用的东西
   
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

SACC2019中国系统架构师大会

【数字转型 架构演进】SACC2019中国系统架构师大会
2019年10月31日~11月2日第11届中国系统架构师大会(SACC2019)将在北京隆重召开。四大主线并行的演讲模式,1个主会场、20个技术专场、超千人参与的会议规模,100+来自互联网、金融、制造业、电商等领域的嘉宾阵容,将为广大参会者提供一场最具价值的技术交流盛会。




----------------------------------------

大会官网>>
  

北京盛拓优讯信息技术有限公司. 版权所有 16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122
中国互联网协会会员  联系我们:huangweiwei@it168.com
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP