关于快速排序法

qdqiqi

1. 
   
2. 
   
3. #include "istream.h"
   
4. #include "ostream.h"
   
5. 
   
6. void qsort(int[],int,int);
   
7. 
   
8. void main()
   
9. {
   
10.         int a[]={6,2,4,5,1,3};
    
11.         int len=sizeof(a)/sizeof(int);
    
12.         qsort(a,0,len-1);
    
13.         for(int i=0;i<len;i++)
    
14.                 cout<<a[i];
    
15. }
    
16. void qsort(int a[],int left,int right)
    
17. {
    
18.         int pivot,l,r,temp;
    
19.         l=left;
    
20.         r=right;
    
21.         pivot=a[(left+right)/2];
    
22.        
    
23.         while(l<r)
    
24.         {
    
25.                 while(a[l]<pivot) ++l;
    
26.                 while(a[r]>;pivot) --r;
    
27.                 if(l>;=r) break;
    
28.                
    
29.                 temp=a[l];
    
30.                 a[l]=a[r];
    
31.                 a[r]=temp;
    
32.                 ++l; --r;
    
33.                 for(int i=0;i<6;i++)
    
34.                 {
    
35.                         cout<<a[i]<<" ";
    
36.                 }
    
37.                 cout<<endl;
    
38.         }
    
39.         if(l==r) l++;
    
40.         if(left<r) qsort(a,left,l-1);
    
41.         if(l<right) qsort(a,r+1,right);
    
42. }
    

复制代码

在这个程序中对于最后两句有点不明白,
在这个程序中left=0,l和r是数组的两部分,也就是说,left<r恒成立,那么最后一句根本不会被执行,(不知道我说得对不对).那么这一句是不是可以去掉?

knight-yl

不会的，在第一次调用的时候是那样。在递归回来的时候就不成立了。

qdqiqi

不是的,我举过例子试过.而且从我上面的分析上也可以推出最后的那一句不会被执行.  

knight-yl

[quote]原帖由 "qdqiqi"]不是的,我举过例子试过.而且从我上面的分析上也可以推出最后的那一句不会被执行.  [/quote 发表：

没用过，再看看。偶一般都用比快速排序更快的排序

qdqiqi

比快速排序法还快的排序是什么排序法?

雷斯林

快速排序不一定在所有的情况下都是最快的，在我的印象里，只有当排序的集合的元素数目大于一定的值n(好象是20左右)后，快速排序的优势才显现出来

无双

快速排序法对中间元素的取值也有一定要求

如果中间元素取值不好的法
严重影响性能

knight-yl

原帖由 "qdqiqi" 发表：
在这个程序中对于最后两句有点不明白,
在这个程序中left=0,l和r是数组的两部分,也就是说,left<r恒成立,那么最后一句根本不会被执行,(不知道我说得对不对).那么这一句是不是可以去掉?

left<r恒成立也不影响往下走啊！必须走，一定要的。快速排序吗！，差点
中招。

雷斯林

快速排序法是一种“分而治之”的算法，也就是说，将一个大的问题分解成一个个小的问题，逐个解决的方法。
快速排序在每次递归处理中，都将传递给它的元素集合再次分半处理之，最后两句自然是分别处理左、右的两半元素。如果最后一句不执行的话，整个算法就没法完成了。

knight-yl

原帖由 "雷斯林" 发表：
快速排序法是一种“分而治之”的算法，也就是说，将一个大的问题分解成一个个小的问题，逐个解决的方法。
快速排序在每次递归处理中，都将传递给它的元素集合再次分半处理之，最后两句自然是分别处理左、右的两半元..........

噼哩啪啦，噼哩啪啦。鼓掌！