jake1036

快速排序新算法

                                          快速排序

   1 该快速排序以末尾值为基准值，进行排序。
   

     【 p，i】之间的数均小于a[r]  ，
      （i-j） 之间的数均大于a[r]   ，
     【j---r）之间的数未确定

2 代码如下：
  
#include <iostream>
/*
  【 p，i】之间的数均小于a[r] 
  （i-j） 之间的数均大于a[r] 
  【j---r）之间的数未确定 
*/


using namespace std ;

  int partition(int * a , int p , int r) ;
  void qsort(int * a , int p , int n) ;
  int main()
  {
    
    int a [] = {13 , 19 ,9 ,5 , 12 , 8 , 7 ,4 ,21 , 2 , 6 , 11} ;
    int x = partition(a , 0 ,11) ;
    cout<<"pos:"<<x<<endl;
    qsort(a , 0 , 11) ;
    for(int i = 0 ; i < 12 ; i++)
     cout<<a[i]<<" " ;
    cin.get() ;
    return 0 ;    
  }

  int partition(int * a , int p , int r)
  {
    int i = p - 1 , j;
    for(j = p ; j < r ;j++)   //当a[j] > a[r] 时，只需要增加j的值 
    {                         //当a[j] <= a[r]时，首先自增i的值，然后交换a[j]与a[i]，最后自增i的值 
           
      if(a[j] <= a[r])   
      {
        i++ ;
        swap(a[i] , a[j]) ;                
      }
            
    }
    swap(a[i + 1] , a[r]) ;
    
    return i + 1 ;
        
  }
   
   void qsort(int * a , int p , int n)
   { 
     if(p < n)
     {   
       int q = partition(a , p , n);
       qsort(a , p , q - 1) ; 
       qsort(a , q + 1 , n) ; 
     }   
   }

2 以数组首数字为基准值的快排

  
 int beginPartition(int * a , int p , int q)
  {
    int i = p ;
    int j = q ;
    int x = a[p] ;  
    while(i <= j)
      {          
        while(i <= j && a[i] <= x ) i++;     
        while(i <= j && a[j] >= x ) j-- ;
        if(i < j )  
          swap(a[i] , a[j]) ;              
      }  
       return j ;          
  }

  注意：循环内的两个子循环的判断条件，均有 i <= j 的条件。
  因为 i 与 j 必然有重合的一次，若没有重合，则j就不会有小于i的情况。


  注意 返回j的值。 第二种方法只需要交换一次。

posted on 2011-04-01 19:59 kahn 阅读(200) 评论(0)  编辑 收藏 引用 所属分类: 算法相关


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理