快速排序算法的有关问题

快速排序算法的问题
最近写了个快速排序的小程序，在VS2010上测试屡试不爽，今天把它放在ubuntu上测试了一把，非常不爽。不但没有排好序，而且原来数组中的数据也丢失了一部分。代码如下：

void qsort(int v[],int left,int right)
{
int last,i;
if(left >= right)
return;
swap(v+left,v+(left+right)/2);
last = left;
for(i=left+1;i<=right;i++)
if(*(v+left)>*(v+i))
swap(v+(++last),v+i);
swap(v+left,v+last);
qsort(v,left,last-1);
qsort(v,last+1,right);
}

[解决办法]

引用:

已经找出问题了。qsort()本身没什么问题，但是swap()出问题了。下面列举两个版本的swap函数，大家看看有什么不同。
版本一：

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

版本二：

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

先不看这两个函数有什么漏洞，单就功能上说有什么区别呢？我原先出问题是因为用的版本一，换了版本二之后就可以排好序了。

大家给分析一下。。。。。

当a == b（地址相同）的时候你直接把它清零了。
[解决办法]

#include <stdio.h>
#define SWAP(a,b) do ((&(a))!=(&(b)))?((a)^=(b)^=(a)^=(b)):((a)=(a)); while (0)
char   *p1="1" ,*p2="2" ;
char    c1=1   , c2=2   ;
short   s1=1   , s2=2   ;
int     i1=1   , i2=2   ;
__int64 I1=1i64, I2=2i64;
float   f1=1.0f, f2=2.0f;
double  d1=1.0 , d2=2.0 ;
void main() {
    SWAP((int)p1,(int)p2);                printf("char *     %5s,   %5s\n",p1,p2);
    SWAP(c1,c2);                          printf("char       %5d,   %5d\n",c1,c2); 
 
    SWAP(s1,s2);                          printf("short      %5d,   %5d\n",s1,s2);
    SWAP(i1,i2);                          printf("int        %5d,   %5d\n",i1,i2);
    SWAP(I1,I2);                          printf("__int64 %5I64d,%5I64d\n",I1,I2);
    SWAP(*(int     *)&f1,*(int     *)&f2);printf("float      %5g,   %5g\n",f1,f2);
    SWAP(*(__int64 *)&d1,*(__int64 *)&d2);printf("double    %5lg,  %5lg\n",d1,d2);

    SWAP(c1,c1);
    printf("%d\n",c1);
}
//char *         2,       1
//char           2,       1
//short          2,       1
//int            2,       1
//__int64     2,    1
//float          2,       1
//double        2,      1
//2

查看更多 下一篇