`
water84222
  • 浏览: 377387 次
  • 性别: Icon_minigender_1
  • 来自: 大连
社区版块
存档分类
最新评论

各种排序算法java实现

算法JavaJ#Blog 
阅读更多
原文地址 http://blog.csdn.net/lschou520/archive/2008/10/29/3176422.aspx
插入排序:
 
  1. package  org.rut.util.algorithm.support;
  2. import  org.rut.util.algorithm.SortUtil;
  4. public   class  InsertSort  implements  SortUtil.Sort{
  5.      /* (non-Javadoc)
  6.      * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
  7.      */
  8.      public   void  sort( int [] data) {
  9.          int  temp;
  10.          for ( int  i= 1 ;i<data.length;i++){
  11.              for ( int  j=i;(j> 0 )&&(data[j]<data[j- 1 ]);j--){
  12.                 SortUtil.swap(data,j,j- 1 );
  13.             }
  14.         }        
  15.     }
  16. }
冒泡排序:
 
  1. package  org.rut.util.algorithm.support;
  2. import  org.rut.util.algorithm.SortUtil;
  4. public   class  BubbleSort  implements  SortUtil.Sort{
  5.      /* (non-Javadoc)
  6.      * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
  7.      */
  8.      public   void  sort( int [] data) {
  9.          int  temp;
  10.          for ( int  i= 0 ;i<data.length;i++){
  11.              for ( int  j=data.length- 1 ;j>i;j--){
  12.                  if (data[j]<data[j- 1 ]){
  13.                     SortUtil.swap(data,j,j- 1 );
  14.                 }
  15.             }
  16.         }
  17.     }
  18. }
选择排序:
  1. package  org.rut.util.algorithm.support;
  2. import  org.rut.util.algorithm.SortUtil;
  4. public   class  SelectionSort  implements  SortUtil.Sort {
  5.      /*
  6.      * (non-Javadoc)
  7.      * 
  8.      * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
  9.      */
  10.      public   void  sort( int [] data) {
  11.          int  temp;
  12.          for  ( int  i =  0 ; i < data.length; i++) {
  13.              int  lowIndex = i;
  14.              for  ( int  j = data.length -  1 ; j > i; j--) {
  15.                  if  (data[j] < data[lowIndex]) {
  16.                     lowIndex = j;
  17.                 }
  18.             }
  19.             SortUtil.swap(data,i,lowIndex);
  20.         }
  21.     }
  22. }
Shell排序:
  1. package  org.rut.util.algorithm.support;
  2. import  org.rut.util.algorithm.SortUtil;
  4. public   class  ShellSort  implements  SortUtil.Sort{
  5.      /* (non-Javadoc)
  6.      * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
  7.      */
  8.      public   void  sort( int [] data) {
  9.          for ( int  i=data.length/ 2 ;i> 2 ;i/= 2 ){
  10.              for ( int  j= 0 ;j<i;j++){
  11.                 insertSort(data,j,i);
  12.             }
  13.         }
  14.         insertSort(data, 0 , 1 );
  15.     }
  16.      /**
  17.      * @param data
  18.      * @param j
  19.      * @param i
  20.      */
  21.      private   void  insertSort( int [] data,  int  start,  int  inc) {
  22.          int  temp;
  23.          for ( int  i=start+inc;i<data.length;i+=inc){
  24.              for ( int  j=i;(j>=inc)&&(data[j]<data[j-inc]);j-=inc){
  25.                 SortUtil.swap(data,j,j-inc);
  26.             }
  27.         }
  28.     }
  29. }
快速排序:
  1. package  org.rut.util.algorithm.support;
  2. import  org.rut.util.algorithm.SortUtil;
  4. public   class  QuickSort  implements  SortUtil.Sort{
  5.      /* (non-Javadoc)
  6.      * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
  7.      */
  8.      public   void  sort( int [] data) {
  9.         quickSort(data, 0 ,data.length- 1 );        
  10.     }
  11.      private   void  quickSort( int [] data, int  i, int  j){
  12.          int  pivotIndex=(i+j)/ 2 ;
  13.          //swap
  14.         SortUtil.swap(data,pivotIndex,j);
  15.         
  16.          int  k=partition(data,i- 1 ,j,data[j]);
  17.         SortUtil.swap(data,k,j);
  18.          if ((k-i)> 1 ) quickSort(data,i,k- 1 );
  19.          if ((j-k)> 1 ) quickSort(data,k+ 1 ,j);
  20.         
  21.     }
  22.      /**
  23.      * @param data
  24.      * @param i
  25.      * @param j
  26.      * @return
  27.      */
  28.      private   int  partition( int [] data,  int  l,  int  r, int  pivot) {
  29.          do {
  30.             while (data[++l]<pivot);
  31.             while ((r!= 0 )&&data[--r]>pivot);
  32.            SortUtil.swap(data,l,r);
  33.         }
  34.          while (l<r);
  35.         SortUtil.swap(data,l,r);        
  36.          return  l;
  37.     }
  38. }
改进后的快速排序:
  1. package  org.rut.util.algorithm.support;
  2. import  org.rut.util.algorithm.SortUtil;
  4. public   class  ImprovedQuickSort  implements  SortUtil.Sort {
  5.      private   static   int  MAX_STACK_SIZE= 4096 ;
  6.      private   static   int  THRESHOLD= 10 ;
  7.      /* (non-Javadoc)
  8.      * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
  9.      */
  10.      public   void  sort( int [] data) {
  11.          int [] stack= new   int [MAX_STACK_SIZE];
  12.         
  13.          int  top=- 1 ;
  14.          int  pivot;
  15.          int  pivotIndex,l,r;
  16.         
  17.         stack[++top]= 0 ;
  18.         stack[++top]=data.length- 1 ;
  19.         
  20.          while (top> 0 ){
  21.              int  j=stack[top--];
  22.              int  i=stack[top--];
  23.             
  24.             pivotIndex=(i+j)/ 2 ;
  25.             pivot=data[pivotIndex];
  26.             
  27.             SortUtil.swap(data,pivotIndex,j);
  28.             
  29.              //partition
  30.             l=i- 1 ;
  31.             r=j;
  32.              do {
  33.                  while (data[++l]<pivot);
  34.                  while ((r!= 0 )&&(data[--r]>pivot));
  35.                 SortUtil.swap(data,l,r);
  36.             }
  37.              while (l<r);
  38.             SortUtil.swap(data,l,r);
  39.             SortUtil.swap(data,l,j);
  40.             
  41.              if ((l-i)>THRESHOLD){
  42.                 stack[++top]=i;
  43.                 stack[++top]=l- 1 ;
  44.             }
  45.              if ((j-l)>THRESHOLD){
  46.                 stack[++top]=l+ 1 ;
  47.                 stack[++top]=j;
  48.             }
  49.             
  50.         }
  51.          //new InsertSort().sort(data);
  52.         insertSort(data);
  53.     }
  54.      /**
  55.      * @param data
  56.      */
  57.      private   void  insertSort( int [] data) {
  58.          int  temp;
  59.          for ( int  i= 1 ;i<data.length;i++){
  60.              for ( int  j=i;(j> 0 )&&(data[j]<data[j- 1 ]);j--){
  61.                 SortUtil.swap(data,j,j- 1 );
  62.             }
  63.         }       
  64.     }
  65. }
归并排序:
  1. package  org.rut.util.algorithm.support;
  2. import  org.rut.util.algorithm.SortUtil;
  4. public   class  MergeSort  implements  SortUtil.Sort{
  5.      /* (non-Javadoc)
  6.      * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
  7.      */
  8.      public   void  sort( int [] data) {
  9.          int [] temp= new   int [data.length];
  10.         mergeSort(data,temp, 0 ,data.length- 1 );
  11.     }
  12.     
  13.      private   void  mergeSort( int [] data, int [] temp, int  l, int  r){
  14.          int  mid=(l+r)/ 2 ;
  15.          if (l==r)  return  ;
  16.         mergeSort(data,temp,l,mid);
  17.         mergeSort(data,temp,mid+ 1 ,r);
  18.          for ( int  i=l;i<=r;i++){
  19.             temp[i]=data[i];
  20.         }
  21.          int  i1=l;
  22.          int  i2=mid+ 1 ;
  23.          for ( int  cur=l;cur<=r;cur++){
  24.              if (i1==mid+ 1 )
  25.                 data[cur]=temp[i2++];
  26.              else   if (i2>r)
  27.                 data[cur]=temp[i1++];
  28.              else   if (temp[i1]<temp[i2])
  29.                 data[cur]=temp[i1++];
  30.              else
  31.                 data[cur]=temp[i2++];            
  32.         }
  33.     }
  34. }
改进后的归并排序:
 
  1. package  org.rut.util.algorithm.support;
  2. import  org.rut.util.algorithm.SortUtil;
  4. public   class  ImprovedMergeSort  implements  SortUtil.Sort {
  5.      private   static   final   int  THRESHOLD =  10 ;
  6.      /*
  7.      * (non-Javadoc)
  8.      * 
  9.      * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
  10.      */
  11.      public   void  sort( int [] data) {
  12.          int [] temp= new   int [data.length];
  13.         mergeSort(data,temp, 0 ,data.length- 1 );
  14.     }
  15.      private   void  mergeSort( int [] data,  int [] temp,  int  l,  int  r) {
  16.          int  i, j, k;
  17.          int  mid = (l + r) /  2 ;
  18.          if  (l == r)
  19.              return ;
  20.          if  ((mid - l) >= THRESHOLD)
  21.             mergeSort(data, temp, l, mid);
  22.          else
  23.             insertSort(data, l, mid - l +  1 );
  24.          if  ((r - mid) > THRESHOLD)
  25.             mergeSort(data, temp, mid +  1 , r);
  26.          else
  27.             insertSort(data, mid +  1 , r - mid);
  28.          for  (i = l; i <= mid; i++) {
  29.             temp[i] = data[i];
  30.         }
  31.          for  (j =  1 ; j <= r - mid; j++) {
  32.             temp[r - j +  1 ] = data[j + mid];
  33.         }
  34.          int  a = temp[l];
  35.          int  b = temp[r];
  36.          for  (i = l, j = r, k = l; k <= r; k++) {
  37.              if  (a < b) {
  38.                 data[k] = temp[i++];
  39.                 a = temp[i];
  40.             }  else  {
  41.                 data[k] = temp[j--];
  42.                 b = temp[j];
  43.             }
  44.         }
  45.     }
  46.      /**
  47.      * @param data
  48.      * @param l
  49.      * @param i
  50.      */
  51.      private   void  insertSort( int [] data,  int  start,  int  len) {
  52.          for ( int  i=start+ 1 ;i<start+len;i++){
  53.              for ( int  j=i;(j>start) && data[j]<data[j- 1 ];j--){
  54.                 SortUtil.swap(data,j,j- 1 );
  55.             }
  56.         }
  57.     }
  58. }
堆排序:
  1. package  org.rut.util.algorithm.support;
  2. import  org.rut.util.algorithm.SortUtil;
  4. public   class  HeapSort  implements  SortUtil.Sort{
  5.      /* (non-Javadoc)
  6.      * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
  7.      */
  8.      public   void  sort( int [] data) {
  9.         MaxHeap h= new  MaxHeap();
  10.         h.init(data);
  11.          for ( int  i= 0 ;i<data.length;i++)
  12.             h.remove();
  13.         System.arraycopy(h.queue, 1 ,data, 0 ,data.length);
  14.     }
  16.       private   static   class  MaxHeap{
  17.          
  18.         
  19.          void  init( int [] data){
  20.              this .queue= new   int [data.length+ 1 ];
  21.              for ( int  i= 0 ;i<data.length;i++){
  22.                 queue[++size]=data[i];
  23.                 fixUp(size);
  24.             }
  25.         }
  26.          
  27.          private   int  size= 0 ;
  28.          private   int [] queue;
  29.                 
  30.          public   int  get() {
  31.              return  queue[ 1 ];
  32.         }
  33.          public   void  remove() {
  34.             SortUtil.swap(queue, 1 ,size--);
  35.             fixDown( 1 );
  36.         }
  37.          //fixdown
  38.          private   void  fixDown( int  k) {
  39.              int  j;
  40.              while  ((j = k <<  1 ) <= size) {
  41.                  if  (j < size && queue[j]<queue[j+ 1 ])
  42.                     j++; 
  43.                  if  (queue[k]>queue[j])  //不用交换
  44.                      break ;
  45.                 SortUtil.swap(queue,j,k);
  46.                 k = j;
  47.             }
  48.         }
  49.          private   void  fixUp( int  k) {
  50.              while  (k >  1 ) {
  51.                  int  j = k >>  1 ;
  52.                  if  (queue[j]>queue[k])
  53.                      break ;
  54.                 SortUtil.swap(queue,j,k);
  55.                 k = j;
  56.             }
  57.         }
  58.     }
  59. }
SortUtil:
  1. package  org.rut.util.algorithm;
  2. import  org.rut.util.algorithm.support.BubbleSort;
  3. import  org.rut.util.algorithm.support.HeapSort;
  4. import  org.rut.util.algorithm.support.ImprovedMergeSort;
  5. import  org.rut.util.algorithm.support.ImprovedQuickSort;
  6. import  org.rut.util.algorithm.support.InsertSort;
  7. import  org.rut.util.algorithm.support.MergeSort;
  8. import  org.rut.util.algorithm.support.QuickSort;
  9. import  org.rut.util.algorithm.support.SelectionSort;
  10. import  org.rut.util.algorithm.support.ShellSort;
  12. public   class  SortUtil {
  13.      public   final   static   int  INSERT =  1 ;
  14.      public   final   static   int  BUBBLE =  2 ;
  15.      public   final   static   int  SELECTION =  3 ;
  16.      public   final   static   int  SHELL =  4 ;
  17.      public   final   static   int  QUICK =  5 ;
  18.      public   final   static   int  IMPROVED_QUICK =  6 ;
  19.      public   final   static   int  MERGE =  7 ;
  20.      public   final   static   int  IMPROVED_MERGE =  8 ;
  21.      public   final   static   int  HEAP =  9 ;
  22.      public   static   void  sort( int [] data) {
  23.         sort(data, IMPROVED_QUICK);
  24.     }
  25.      private   static  String[] name={
  26.              "insert" , "bubble" , "selection" , "shell" , "quick" , "improved_quick" , "merge" , "improved_merge" , "heap"
  27.     };
  28.     
  29.      private   static  Sort[] impl= new  Sort[]{
  30.              new  InsertSort(),
  31.              new  BubbleSort(),
  32.              new  SelectionSort(),
  33.              new  ShellSort(),
  34.              new  QuickSort(),
  35.              new  ImprovedQuickSort(),
  36.              new  MergeSort(),
  37.              new  ImprovedMergeSort(),
  38.              new  HeapSort()
  39.     };
  40.      public   static  String toString( int  algorithm){
  41.          return  name[algorithm- 1 ];
  42.     }
  43.     
  44.      public   static   void  sort( int [] data,  int  algorithm) {
  45.         impl[algorithm- 1 ].sort(data);
  46.     }
  47.      public   static   interface  Sort {
  48.          public   void  sort( int [] data);
  49.     }
  50.      public   static   void  swap( int [] data,  int  i,  int  j) {
  51.          int  temp = data[i];
  52.         data[i] = data[j];
  53.         data[j] = temp;
  54.     }
  55. }
分享到：
| css
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

Magicbox
Global site tag (gtag.js) - Google Analytics