非比较排序算法

                                                   非比较排序算法

 非比较排序算法，主要包括 基数排序 ，基数排序，桶排序三种方法。
  
 1 基数排序
    该算法的基本思想是确定数组中，小于a[i]的个数，比如说小于a[i]的个数为17，那么a[i]就位于第18的位置上。
    该算法使用了三个数组。A数组作为输入数组，B数组作为目标数组，C[K]数组作为辅助数组。
   算法的复杂度为O(n)，但是要求K的个数不应该太大，否则需要使用大量的存储空间。

   代码如下：
  

/**//*
该算法的本质 是找出比a[i]小的元素，然后就确定了a[i]的位置
当欲排序的数组中，存在相同的元素，就需要修改算法 
*/


#include <iostream>
 using namespace std ;
 
 const int N = 8 ;
 const int K = 6 ;
 void countSort(int a[] , int b[] , int c[]) ;
 
 int main()
 {
    int a[N] ={2 , 5 , 3 , 0 ,2 , 3 , 0 , 3 } ;
    int b[N] = {0};
    int c[K] = {0};
   countSort(a , b ,c) ; 
    for(int i = 0 ; i < N ; i++)
        cout<<b[i]<<" " ;
        cout<<endl ;
    cin.get() ;   
 }
 
 void countSort(int a[] , int b[] , int c[])
 {
    int i = 0 ;  
   for( i = 0 ; i < K ; i++)
      c[i] = 0;
      
   for( i = 0 ; i < N ; i++)   
      c[a[i]] = c[a[i]] + 1  ;               //c数组中存储的是a[i]的个数 
      
   for(i = 1 ; i < K ; i++)
      c[i] = c[i - 1] + c[i] ;   //c数组中存储的是不大于a[i]的个数 
   
   for(i = N - 1 ; i >= 0 ; i--)
   {
     b[c[a[i]] - 1] = a[i] ;                 //此处应该包含 减1操作，因为从0开始计数，b中数为
                                              
      
      c[a[i]] = c[a[i]] - 1 ;              //a数组中有重复的元素，需要将重复元素的位置向前移动一位，以方便相同的数字插入
   }    
 } 

  2 基数排序
     n个数 ，每个数均为d位数，不足的数位用0补足，排序思想为：分别排序每位数字，从最低有效位开始，一直到最高有效位，
    d位数字只需要进行d遍即可完成。
   
    注意 基数排序对各个位上的数字调用的排序算法应该为 稳定排序，归并排序和基数排序均是稳定排序。以下代码采用了插入排序
   
    

#include <iostream>
using namespace std ;
  
  int partition(int * a , int * b , int p , int q) ;
  void qsort(int *a , int * b, int i , int j) ;
  void insertSort(int * a  , int * b , int n) ;
  void radix(int * a , int n , int d) ;
    
    


  int main()
  {
    int a[] = {329 , 457 ,657 , 839 , 436 , 720 , 355} ;  
    radix(a , 7 , 3) ;    
    for(int i = 0 ; i < 7 ; i++)    
        cout<<a[i]<<" " ;
    cin.get() ;     
    return 0 ;    
  } 
 
     //快排为非稳定排序，无法使用 
   int partition(int * a , int * b , int p , int q)
   {
     int i = p - 1 ;
     for(int j = p ; j < q ; j++)
     {
       if(b[j] <= b[q])
        {
          i++ ; //此处i自增非常重要 
          swap(b[i] , b[j]) ;
          swap(a[i] , a[j]) ;       
        }       
     }
     swap(b[i + 1]  , b[q]) ;
     swap(a[i + 1]  , a[q]) ; 
     return i + 1 ;       
   }
    
  


  //2min 内写出一个快速排序 
     void qsort(int *a , int * b, int i , int j)
     {
       if(i < j)   
          {
            int q = partition(a ,b , i , j) ;   
            qsort(a , b , i , q - 1) ;
            qsort(a , b , q + 1 , j) ;   
          }
          
     }
     
     
 /**//*
 
  对数组b调用插入排序 
 */
 void insertSort(int * a  , int * b , int n)
 {
   int i , j ;
   for( i = 0 ; i < n  ;i++)
   {
        int x = b[i] ; 
        int y = a[i] ;
        for(j = i  ; j > 0&&x < b[j - 1] ; j--)
        {                      
          b[j] = b[j - 1] ;
          a[j] = a[j - 1] ;                              
        }
        b[j] = x ;     
        a[j] = y ;     
   }
            
 } 
 
 
 
 
  void radix(int * a , int n , int d)
  {
    //申请一个辅助数组b 
    int * b = new int[n] ;
    int temp = 1 ;
    for(int i = 0 ; i < d ; i++)
    {
      
      for(int j = 0 ; j < n ;j++)  //计算每位上分别的值 
      {
        b[j] =( a[j] / temp ) % 10 ;
            
      }     
        temp *= 10 ; 
       //下面调用稳定排序算法，排序b数组，并按照b数组的大小关系交换a数组      
       insertSort(a , b, n) ;     
    }
      
    delete [] b ;
     b = 0 ;      
  }

     
 3 桶排序 
    该算法有一个前提是，数组中的元素均匀分布在(0,1]之间，按照小数位第一位的数字，将其分配到对应的数组位上。0.72就分配到a[7]上，
    0.22就分配到a[2]上。然后根据小数的数值进行插入排序，最后顺序从a[1]处遍历每一个链表，输出结果。

/**//*
 桶排序，该算法的假设是所有的数字均匀分布在(0 , 1]之上。首先按照小数点第一位的数字划分到10个队列之上 
  然后对每一个队列使用 插入排序，最后顺序输出10个队列，即完成了排序操作
*/

#include <iostream>
 using namespace std ;
 
 typedef struct Node{
    double data ;
    struct Node * link ;    
 }  Node;  //桶排序所使用的链表数据结构 
 
 
 void bucketSort(double * a , Node * list , int n) ;
 
 int main(){
   
   double a[] = {0.78 , 0.17 , 0.39, 0.26 , 0.72 , 0.94 , 0.21, 0.12 , 0.23 ,0.68} ;
   Node list[10] ;
   for(int i = 0 ; i < 10 ; i++)   //初始化数组链表 
    {
      list[i].link = 0 ;
      list[i].data = 0 ;       
    }
     
   bucketSort(a , list , 10) ;    //调用桶排序 
   
    for(int i = 1 ; i < 10 ; i++)    
    {
      Node * h = list[i].link ;
      while(h != 0)
      {
         cout<<" "<<h->data;     
         h = h->link ;     
      }                         
    }      
    cin.get();    
   return 0 ;
 }

  //扫描数组a，去小数点后第一位i,将其插入到对应的链表list[i]处，按照
  //大小插入到适宜的链表位置上 
  void bucketSort(double * a , Node * list , int n) 
  {
    for(int i = 0 ; i < n ; i++)
    {
       int p = (int)( a[i] * 10 );  //获取在链表中的位置 
       Node * h = &list[p];     
       while(h->link != 0)
       {       
        if(a[i] <= h->link->data) //在h->link前插入值 
        {
              
              Node * node = new Node ;
              node->data = a[i] ;              
              node->link = h->link ;
              h->link = node ;  
              break;
        }
        h = h ->link ;                           
       }
       
         if(h->link == 0)
        {
          Node * node = new Node ;
          node->data = a[i] ;
          node->link = 0 ;
          h->link = node ;
          }              
    }       
  }
 

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