universe-xy 2015-07-09 07:50 采纳率: 0%
浏览 1650

在快速排序里,进行数据交换时,遇到的特殊问题

 #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 2015-07-09 17: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);
         }
    
    评论

报告相同问题?

悬赏问题

  • ¥15 MATLAB怎么通过柱坐标变换画开口是圆形的旋转抛物面?
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题
  • ¥15 Visual Studio问题
  • ¥20 求一个html代码,有偿