各种排序算法java实现

原文地址 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. }