3个基本算法的实现技巧

　　问题1：如何不使用中间变量来实现两个整形变量的交换。解决这个问题是思路很多，首先可以用加减法，即

1 void swp(int *x,int *y)
2 {
3     *x=*x+*y;
4     *y=*x-*y;
5     *x=*x-*y;
6 }

其实任何满足互逆运算的运算都可以用来实现两个整形变量的交换。异或运算和乘除运算都可以实现两个整形变量的交换。

异或运算方法如下:

a=a^ b;
b=a^ b;
a=a^ b;

乘除运算方法如下:

a=a*b;
b=a/b;
a=a/b;

由于a,b不能为0，所以有一定的适用范围。

当然也可以这样：

a=(a+b)/2;
b=(a-b)/2;
a=a-b;
b=a+b;

不过看似合理的公式却是实用性不大，因为不同的语言，不同的类型会出现意想不到的情况。

问题2：快速排序的实现

标准的快速排序可以这样写：

 1 int partition(int src[],int lower,int upper)
 2 {
 3     int choosed=src[lower];
 4     while(lower<upper)
 5     {
 6         while(lower<upper&&choosed<=src[upper]) upper--;
 7         if(lower<upper) 
 8         {
 9             int tmp=src[lower];
10             src[lower]=src[upper];
11             src[upper]=tmp;
12         }
13         while(lower<upper&&choosed>=src[lower]) lower++;
14         if(lower<upper) 
15         {
16             int temp=src[lower];
17             src[lower]=src[upper];
18             src[upper]=temp;
19         }
20     }
21     return lower;
22 }
23 void quick_sort(int src[],int lower,int upper)
24 {
25     if(lower<upper)
26     {
27         int mid=partition(src,lower,upper);
28         quick_sort(src,lower,mid-1);
29         quick_sort(src,mid+1,upper);
30     }
31 }

但是实现低位和高位交换的写法有点繁复可以优化为：

 1 int partition(int src[],int lower,int upper)
 2 {
 3     int choosed=src[lower];
 4     while(lower<upper)
 5     {
 6         while(lower<upper&&choosed<=src[upper]) upper--;
 7         if(lower<upper) src[lower]=src[upper];
 8         while(lower<upper&&choosed>=src[lower]) lower++;
 9         if(lower<upper) src[upper]=src[lower];
10 
11         src[lower]=choosed;
12     }
13     return lower;
14 }

问题3：fibonacci数列的实现：

1 int fibonacci(int n)
2 {
3         if (n == 0 || n == 1)
4                 return 1;
5         else
6                 return fibonacci(n-1) + fibonacci(n-2);
7 }

递归方法思路清晰，但是由于递归的效率不高，在可以不用递归的地方尽量用非递归方法。

下面为非递归方法：

 1 int Fibonacci(int n)
 2 {
 3     if(n==1 || n==0) return 1;
 4     int f1=1, f2=1, sum=0;
 5     for(int i=2; i<=n; ++i)
 6     {
 7        sum = f1 + f2;
 8        f1 = f2;
 9        f2 = sum;
10     }
11     return sum;
12 }

这里利用sum变量不断迭代计算累加结果，其实利用两个变量就可以实现：

 1 int fibonacci(int n)
 2 {    
 3     if(n==1||n==0) return 1;
 4     int y=1;int x=1;
 5     for(int i=1;i<n;i++)
 6     {
 7         y=x+y;
 8         x=y-x;
 9     }
10     return y;
11 }

　　当然累加实现写成一行效果也一样：

1 x,y=y,x+y
2 return x