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);
         }
    
    评论

报告相同问题?

悬赏问题

  • ¥40 复杂的限制性的商函数处理
  • ¥15 程序不包含适用于入口点的静态Main方法
  • ¥15 素材场景中光线烘焙后灯光失效
  • ¥15 请教一下各位,为什么我这个没有实现模拟点击
  • ¥15 执行 virtuoso 命令后,界面没有,cadence 启动不起来
  • ¥50 comfyui下连接animatediff节点生成视频质量非常差的原因
  • ¥20 有关区间dp的问题求解
  • ¥15 多电路系统共用电源的串扰问题
  • ¥15 slam rangenet++配置
  • ¥15 有没有研究水声通信方面的帮我改俩matlab代码