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 请问这个是什么意思?
  • ¥15 STM32驱动继电器
  • ¥15 Windows server update services
  • ¥15 关于#c语言#的问题:我现在在做一个墨水屏设计,2.9英寸的小屏怎么换4.2英寸大屏
  • ¥15 模糊pid与pid仿真结果几乎一样
  • ¥15 java的GUI的运用
  • ¥15 我想付费需要AKM公司DSP开发资料及相关开发。
  • ¥15 怎么配置广告联盟瀑布流
  • ¥15 Rstudio 保存代码闪退
  • ¥20 win系统的PYQT程序生成的数据如何放入云服务器阿里云window版?