首页 > C/C++语言 > C/C++数据结构 > 小弟很菜,请教个快速排序问题
2010
05-30

小弟很菜,请教个快速排序问题

#include”stdio.h”
int middle(int *a,int low,int high,int middle)//将数列中的开始,末尾,中间进行比较,取三者中间值作为枢轴
{int v;
v=a[low]>a[high]?a[low]>a[middle]?a[middle]>a[high]?middle:high
     :low                            
         :a[high]>a[middle]?a[middle]>a[low]?middle:low
      :high;
return v;}
int Qviod(int *a,int low,int high,int *nl,int *nh)
{int temp;
 int v,ae;
 nl=nh=0;
 v=middle(a,low,high,(high+low)/2);
 if(v!=low)    {temp=a[v];a[v]=a[low];a[low]=temp;}//若这句执行,结果总会有一个较小的数被排序在一个较大的数后面,不知道为什么
 temp=a[low];
 while(low<high)
 {while(low<high&&a[high]>temp)
 {if(a[high]<a[high-1] ){ae=a[high];a[high]=a[high-1];a[high-1]=ae;nh++;}//同时进行冒泡排序,如果nh的值为0,则说明右边部分已经有序,
   high–;}
   a[low]=a[high];
   while(low<high&&a[low]<temp)
 {if(a[low]>a[low+1] ){ae=a[low];a[low]=a[low+1];a[low+1]=ae;nl++;}//同上
   low++;}
   a[high]=a[low];
 }
 a[low]=temp;
 return low;
}
void Digui(int *a,int low,int high)
{int nl,nh;
 int middle;
 middle=Qviod(a,low,high,&nl,&nh);
 if(low<high)
 {if(nl==0&&nh==0);//下面通过nh、nl的值判断再对哪部分进行快速排序
  else if(nl==0)  Digui(a,middle+1,high);
         else if(nh==0) Digui(a,low,middle-1);
                else if(middle-low<=high-middle)
  {Digui(a,low,middle-1);Digui(a,middle+1,high);}
               else
  {Digui(a,middle+1,high);Digui(a,low,middle-1);}
 }//if
 }//Digui
main()
{int a[10]={38,27,96,15,32,56,87,46,61,73},i;
 Digui(a,0,9);
 for(i=0;i<10;i++)
 printf(“%3d”,a);
}


小弟很菜,请教个快速排序问题》有 3 条评论

  1. xjpCC 说:

    middle函数逻辑没问题,以上程序的主要目的就是提高快速排序的效率,如果不执行

    v=middle(a,low,high,(high+low)/2);  
    if(v!=low)    {temp=a[v];a[v]=a[low];a[low]=temp;}
    这两句,一切都正确。但如执行了,结果就变成了15 27 32 38 46 56 61 87 73 96,不知道哪里错了。
    我应该做些什么?
  2. 大仙 说:

    上楼说的好

留下一个回复