今天上午听同学说不用中间变量怎么交换两个变量的值,下面就罗列了几种交换值的方法,并且测试了交换变量值方法的效率。
方法一:
通过临时变量实现,也是最常见的方法:
void swap(int a ,int b)
{
int t;
t=a;
a=b;
b=t;
}
t作为临时变量进行交换。这种算法易于理解,效率也很高。
方法二:
算术运算,就是通过普通的+和-运算来实现:
void swap(int a ,int b)
{
a=b-a; //a=20;b=30
b=b-a; //a=20;b=10
a=b+a; //a=30;b=10
}
证 明:把a、b看做数轴上的点,围绕两点间的距离来进行计算。第一句“a=b-a”求出ab两点的距离,并且将其保存在a中;第二句“b=b-a”求出a到原点的距离(b到原点的距离与ab两点距离之差),并且将其保存在b中;第三句“a=b+a”求出b到原点的距离(a到原点距离与ab两点距离之和),并 且将其保存在a中。完成交换。 此算法与方法一相比,多了三个计算的过程,没有借助临时变量。
当然你也可以写成这样:
void swap(int a ,int b)
{
a=b+a;
b=b-a;
a=b-a;
}
当然也可以这样:
void swap(int a ,int b) {
a=b-a;
b=b-a;
a=b+a;
}
同上面一个意思。
缺点:很可能造成溢出,需要加以判断。
方法三:
原理为算术运算符的结合顺序为自左至右:
void swap(int a ,int b)
{
a=b+(b=a)*0;
}
我学习c#不久暂时无法解释,请读者自行参考其他高手的博客。
方法四:
通过异或运算实现变量的交换
void swap(int a ,int b)
{
a=a^b;
b=a^b;
a=a^b;
}
很多人认为最为神奇,其实不然,我测试了一下,它的效率是这几个中效率最低的。老师讲这是哪个公司的面试题,但是你会发现花哨 != 高端,我想没有人会把它放进项目中。
下面是我用自己的电脑做了一个测试:
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace C排序 { class Program {
/// <summary> /// 算数交换 /// </summary> /// <param name="a"></param> #region static void mathcmp(ref int[] a) { for (int i = 0; i < a.Length - 1; i++) { for (int j = 0; j < a.Length - 1 - i; j++) { if (a[j] > a[j + 1]) { a[j] = a[j + 1] + a[j] ; a[j+1] = a[j] - a[j + 1]; a[j] = a[j] - a[j + 1]; } } } } #endregion
/// <summary> /// 算数交换 /// </summary> /// <param name="a"></param> #region static void mathcmp(ref int[] a) { for (int i = 0; i < a.Length - 1; i++) { for (int j = 0; j < a.Length - 1 - i; j++) { if (a[j] > a[j + 1]) { a[j] = a[j + 1] + a[j] ; a[j+1] = a[j] - a[j + 1]; a[j] = a[j] - a[j + 1]; } } } } #endregion
/// <summary> /// 语言特性交换两个数的值 /// </summary> /// <param name="a">传入数组的名称</param> #region static void effcmp(ref int[] a) { for (int i = 0; i < a.Length - 1; i++) { for (int j = 0; j < a.Length - 1 - i; j++) { if (a[j] > a[j + 1]) { a[j] = a[j + 1] + (a[j + 1] = a[j]) * 0; } } } } #endregion
/// <summary> /// 冒泡抑或排序 /// 从小到大排序 /// </summary> /// <param name="a">传入数组的名称</param> #region static void yihuomp(ref int[] a) { for (int i = 0; i < a.Length - 1; i++) { for (int j = 0; j < a.Length - 1 - i; j++) { if (a[j] > a[j + 1]) { a[j] = a[j] ^ a[j + 1]; //抑或交换两个数的值 a[j + 1] = a[j] ^ a[j + 1]; a[j] = a[j] ^ a[j + 1]; } } } } #endregion static void fuzhi(ref int[] a) { for (int i = 0; i < a.Length; i++) { a[i] = a.Length-i; } }
static void Main(string[] args) { int[] arry = new int[80000]; fuzhi(ref arry); DateTime d1 = DateTime.Now; mp(ref arry); DateTime d2 = DateTime.Now; Console.WriteLine("冒泡“方法一中间变量”排序结束 用时:{0}\n", d2-d1); fuzhi(ref arry); DateTime d7 = DateTime.Now; effcmp(ref arry); DateTime d8 = DateTime.Now; Console.WriteLine("冒泡“方法二算数”排序结束 用时:{0}\n", d8 - d7); fuzhi(ref arry); DateTime d5 = DateTime.Now; effcmp(ref arry); DateTime d6 = DateTime.Now; Console.WriteLine("冒泡“方法三语言特性”排序结束 用时:{0}\n", d6 - d5); fuzhi(ref arry); DateTime d3 = DateTime.Now; yihuomp(ref arry); DateTime d4 = DateTime.Now; Console.WriteLine("冒泡“方法四抑或”排序结束 用时:{0}", d4 - d3); Console.ReadKey(); }
} }
下图是用一个有80000个数据的数组排序得到的时间,只是在我的电脑上测试了可能不是很准确,但是应该可以供给大家做参考。很显然抑或交换是效率最差的。