2 u014643765 u014643765 于 2015.07.09 15:50 提问

在快速排序里,进行数据交换时,遇到的特殊问题
 #include<stdio.h>
#include<stdlib.h>
#include<time.h>

//////////////快速排序///////////////////
void quicksort(int* src,int start,int end)
{
    int l=start,r=end;
    int key=0;
    int mid=0;
    if(start>=end)
        return;
///////这段代码无法得到预期的结果////////////////
#if 1
    mid=(start+end)/2; printf("%d %d +++++++++>%d\n",src[mid],src[l],mid);
//    key=src[mid];
    src[l]=src[l]+src[mid]; printf("%d %d===",src[l],src[mid]);//会出现两个数相等情况,但不是0
    src[mid]=src[l]-src[mid]; printf("%d %d\n",src[l],src[mid]);//当上面出现相等情况时,这里两个数为0
    src[l]=src[l]-src[mid]; printf("%d %d %d ------->%d\n\n",src[l],key,src[mid],mid);
    key=src[l];
#endif
//key=src[mid];最后可以得到正确的排序结果,key=src[l];会改变原数组中的数据。key必须初始化
#if 0
    key=src[l];
    src[l]=src[(start+end)/2];
    src[(start+end)/2]=key;
#endif
    while(l<r)
    {
        while((l<r)&&(key<=src[r]))
            r--;
        if(l<r)
            src[l++]=src[r];
        while((l<r)&&(key>=src[l]))
            l++;
        if(l<r)
            src[r--]=src[l];
    }
    src[l]=key;
    quicksort(src,start,l-1);
    quicksort(src,l+1,end);
}

int main(void)
{
    int* src=NULL;
    int n=30;
    int i=0;
    clock_t start,end;
    double duration;

    src=(int*)malloc(n*sizeof(int));
    for(i=0;i<n;i++)
        src[i]=rand();
    start=clock();
    quicksort(src,0,n-1);
    end=clock();
    duration=(end-start)*1000/CLOCKS_PER_SEC;
    printf("耗时%f毫秒\n\n",duration);

    for(i=n-30;i<n;i++)
    {
        printf("%d=%d\t",i,src[i]);
        if(i%6==0)
            putchar('\n');
    }
    free(src);
    return 0;
}

1个回答

GKatHere
GKatHere   2015.07.10 01:03
  if (start != mid)        // 添加......其实交不交换一个样
     {
     src[l]=src[l]+src[mid]; printf("%d %d===",src[l],src[mid]);//会出现两个数相等情况,但不是0
     src[mid]=src[l]-src[mid]; printf("%d %d\n",src[l],src[mid]);//当上面出现相等情况时,这里两个数为0
     src[l]=src[l]-src[mid]; printf("%d %d %d ------->%d\n\n",src[l],key,src[mid],mid);
     }
Csdn user default icon
上传中...
上传图片
插入图片