Taken from< http://deng5566.iteye.com/blog/678817 >For self-study only.

Sorting Algorithm Review (Java Implementation) (1): Insertion, Bubbling, Selection, Shell, To facilitate management, a basic class is introduced for quick sorting:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
package algorithms;   

/**  * @author yovn  **/ 

public abstract class Sorter<E extends Comparable<E>> {       
	public abstract void sort(E[] array,int from ,int len);       
	public final void sort(E[] array)     {         
		sort(array,0,array.length);     
	}     
	
	protected final void swap(E[] array,int from ,int to) {         
		E tmp=array[from];         
		array[from]=array[to];         
		array[to]=tmp;    
	}   
}

The insertion sorting algorithm is very efficient when the data size is small. The algorithm inserts a suitable position from the K+1th to the top K ordered arrays each time, with K starting from 0 to N-1, to complete the sorting:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
package algorithms; 

/**  * @author yovn **/ 

public class InsertSorter<E extends Comparable<E>> extends Sorter<E> {      
    public void sort(E[] array, int from, int len) {          
    	E tmp=null;           
    	for(int i=from+1;i<from+len;i++) {               
    		tmp=array[i];               
    		int j=i;               
    		for(;j>from;j--) {                   				if(tmp.compareTo(array[j-1])<0) {                       					array[j]=array[j-1];                   
    				} else break;               
    		}               
    		
    		array[j]=tmp;           
    	}     
    }       
}  

Bubble sort is perhaps the simplest sorting algorithm, which compares adjacent elements starting from the end of the array and bubbles the i-th element to the i-th position of the array. Sort from 0 to N-1 to complete the sorting. (Of course, you can also start comparing adjacent elements from the beginning of the array and bubble the i-th largest element to the N-i-th position of the array.). Sort from 0 to N-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

package algorithms;   

/**  * @author yovn  **/ 

public class BubbleSorter<E extends Comparable<E>> extends Sorter<E> { 
      private static  boolean DWON=true;
      public final void bubble_down(E[] array, int from, int len) {         			for(int i=from;i<from+len;i++) {             
      			for(int j=from+len-1;j>i;j--) {                 					if(array[j].compareTo(array[j-1])<0) {                     						swap(array,j-1,j);                 
      				}             
      			}         
      		}     
      	}       
      	
      	public final void bubble_up(E[] array, int from, int len) {    
      	     for(int i=from+len-1;i>=from;i--) {             
      	     	for(int j=from;j<i;j++) {                 
      	     		if(array[j].compareTo(array[j+1])>0) {                     						swap(array,j,j+1);                 
      	     		}             
      	     	}         
      	     }     
      	}     
      	
      	@Override     
      	public void sort(E[] array, int from, int len) {           
      		if(DWON) {             
      			bubble_down(array,from,len);         
      		} else {             
      			bubble_up(array,from,len);         
      		}     
      	}   
}  

3、 Compared to bubble sorting, selection sorting does not swap every time a reverse order is found. Instead, it records the position of the i-th element when it is found globally, and finally swaps it with the i-th element to ensure the final order of the array. Compared to insertion sorting, selection sorting always selects the i-th smallest element globally and does not adjust the first i elements.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
package algorithms; 
/**  * @author yovn  **/ 
public class SelectSorter<E extends Comparable<E>> extends Sorter<E> {     
    @Override     
 	public void sort(E[] array, int from, int len) {         
 		for(int i=0;i<len;i++)         {             
 			int smallest=i;             
 			int j=i+from;             
 			for(;j<from+len;j++) {  
 			    if(array[j].compareTo(array[smallest])<0) {   
 			        smallest=j;                 
 				}             
 			}             
 		
 			swap(array,i,smallest);           
 		}       
 	}   
 }

Shell sorting can be understood as a variant of insertion sorting, which fully utilizes two characteristics of insertion sorting:

*Very efficient when the data scale is small
*The time cost when the given data is already ordered is O (N)

So, Shell sort divides the data into several small blocks each time, using insertion sort, and then combines them into larger blocks after these small blocks are sorted, continuing to use insertion sort, constantly merging the small blocks until they are finally merged into one block, and using insertion sort. The division into several small blocks here is controlled by “increment”. At the beginning, the increment is relatively large, close to N/2, so that the divided small blocks are close to N/2, gradually decreasing the “increment” until it reaches 1. The always good increment sequence is 2 ^ k-1,2 ^ (k-1) -1,…, 7,3,1, which can make the time complexity of Shell sorting reach O (N ^ 1.5), so I used this increment sequence when implementing Shell sorting

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 package algorithms;   
 /**  * @author yovn  **/ 
 
 public class ShellSorter<E extends Comparable<E>> extends Sorter<E>  {       /* (non-Javadoc)      * Our delta value choose 2^k-1,2^(k-1)-1,  .7,3,1.      * complexity is O(n^1.5)      * @see algorithms.Sorter#sort(E[], int, int)      */     
 
 	@Override     
 	public void sort(E[] array, int from, int len) {           
 		//1.calculate  the first delta value;         
 		int value=1;         
 		while((value+1)*2<len) {             
 			value=(value+1)*2-1;           
 		}           
 		
 		for(int delta=value;delta>=1;delta=(delta+1)/2-1) {             
 			for(int i=0;i<delta;i++) {
 			    modify_insert_sort(array,from+i,len-i,delta);            
 			}         
 		}       
 	}       
 	
 	private final  void modify_insert_sort(E[] array, int from, int len,int delta) {           
 		if(len<=1)return;           
 		E tmp=null;           
 		for(int i=from+delta;i<from+len;i+=delta)           {               			tmp=array[i];              
			int j=i;               
			for(;j>from;j-=delta)               {                   				if(tmp.compareTo(array[j-delta])<0) {                       					array[j]=array[j-delta];                  
				 }                   
				 else break;               
			}               
			
			array[j]=tmp;           
		}       
	} 
}

Quick sort is currently the most widely used sorting algorithm. Generally, it is divided into the following steps:

*Choose a hub element (there is a good selection method, in my implementation I use a simple method of removing intermediate elements)
*Use this pivot element to split the array so that elements smaller than it are on its left and elements larger than it are on its right. And place the hub elements in the appropriate positions.
*According to the final determined position of the hub element, divide the array into three parts: the left part, the right part, and the hub element itself. recursively call the quicksort algorithm for the left and right parts respectively.

The core of quicksort lies in the segmentation algorithm, which can also be said to be the most skillful part.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
package algorithms;   
/**  * @author yovn  **/ 

public class QuickSorter<E extends Comparable<E>> extends Sorter<E> {           @Override     
	public void sort(E[] array, int from, int len) { 
	    q_sort(array,from,from+len-1);     
	}         
	
	private final void q_sort(E[] array, int from, int to) {         
		if(to-from<1)
			return;         
			
		int pivot=selectPivot(array,from,to);  
		pivot=partion(array,from,to,pivot);              
		
		q_sort(array,from,pivot-1);         
		q_sort(array,pivot+1,to);       
	}         
	
	private int partion(E[] array, int from, int to, int pivot) {         
		E tmp=array[pivot];         
		array[pivot]=array[to];//now to's position is available   
		while(from!=to) {             	
			while(from<to&&array[from].compareTo(tmp)<=0)
				from++;  
			   
			if(from<to)  {                 
				array[to]=array[from];//now from's position is available                 		to--;             
			}             
			     
			while(from<to&&array[to].compareTo(tmp)>=0)
			   to--;             
			     	
			if(from<to) {                 
				array[from]=array[to];//now to's position is available now  
             from++;             
          }         
      }         
          
      array[from]=tmp;         
          
      return from;     
 	}         
      
	 private int selectPivot(E[] array, int from, int to) {           
	      return (from+to)/2;     
	 }   
}  

The idea of the six merge sort algorithm is to divide the sequence to be sorted into two parts each time, recursively use merge sort on each part, and merge these two sub parts into one sequence after completion. Merge sort utilizes a global temporary array to facilitate the merging of subsequences, and the core of this algorithm lies in merging.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 package algorithms;   
 
 import java.lang.reflect.Array;   
 
 public class MergeSorter<E extends Comparable<E>> extends Sorter<E>  {  
       @SuppressWarnings("unchecked")     
       @Override     
       public void sort(E[] array, int from, int len) {      
          if(len<=1)
          	return;  
          E[] temporary=(E[])Array.newInstance(array[0].getClass(),len);   
          merge_sort(array,from,from+len-1,temporary);       
       }       
       
       private final void merge_sort(E[] array, int from, int to, E[] temporary) {         
	       	if(to<=from) {             
	       		return;         
	       	}         
	       	
	       	int middle=(from+to)/2;
	       	merge_sort(array,from,middle,temporary);  
	       	merge_sort(array,middle+1,to,temporary); 
	       	merge(array,from,to,middle,temporary);     
       }       
       
       private final void merge(E[] array, int from, int to, int middle, E[] temporary) {                
	       	int k=0,leftIndex=0,rightIndex=to-from; 
	       	System.arraycopy(array, from, temporary, 0, middle-from+1);    
	       	for(int i=0;i<to-middle;i++) {             
	       		temporary[to-from-i]=array[middle+i+1];         
	       	}         
	       	
	       	while(k<to-from+1) {           
	       	  if(temporary[leftIndex].compareTo(temporary[rightIndex])<0) {  
	       	      array[k+from]=temporary[leftIndex++];               
	       	  } else {                 
	       	  	   array[k+from]=temporary[rightIndex--];          
	            }             
	            
	            k++;         
	          }       
        }   
 }

The seven heap sorting heap is a completely binary tree, usually implemented using arrays. There are two main core operations of the heap,

*Shift Up from the specified node
*Shift Down from the specified node

Building a heap and deleting fixed nodes in the heap use shiftDoon, while inserting nodes is usually done in combination with both operations. Heap sorting is achieved using the maximum value heap. The i-th time the maximum value is removed from the top of the heap and placed at the i-th to last position of the array, then shifted down to the i+1th to last position. A total of N adjustments are performed to complete the sorting. Obviously, heap sorting is also a selective sorting method, selecting the i-th largest element each time.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
 package algorithms;   
 
 public class HeapSorter<E extends Comparable<E>> extends Sorter<E>  {     
     @Override     
     public void sort(E[] array, int from, int len) {   
           build_heap(array,from,len);           
           for(int i=0;i<len;i++) {
           	//swap max value to the (len-i)-th position   
           	swap(array,from,from+len-1-i);  
           	shift_down(array,from,len-1-i,0);//always shiftDown from 0  
           }     
     }       
     
     
     private final void build_heap(E[] array, int from, int len) {    
          int pos=(len-1)/2;//we start from (len-1)/2, because branch's node +1=leaf's node, and all leaf node is already a heap         
          for(int i=pos;i>=0;i--)         {     
               shift_down(array,from,len,i);         
          }       
     }       
     
     private final void shift_down(E[] array,int from, int len, int pos){ 
     		E tmp=array[from+pos];         
     		int index=pos*2+1;//use left child 
     		while(index<len)//until no child  {
     	        if(index+1<len&&array[from+index].compareTo(array[from+index+1])<0)//right child is bigger             {
     			    index+=1;//switch to right child             
    	    	}             
      	
			   	if(tmp.compareTo(array[from+index])<0)             {   
			    	array[from+pos]=array[from+index];                 
			       pos=index;                 
			      	index=pos*2+1;               
			   }  else {                
			     	break;            
			   }        
   			}         
 
    		array[from+pos]=tmp;       
   	}     
 }

Bucket sorting is no longer based on comparison, and it belongs to the same allocation class as cardinality sorting. The characteristic of this type of sorting is to know some features of the sequence to be sorted in advance. Bucket sorting requires prior knowledge that the sequence to be sorted falls within a certain range, and this range should not be very large. For example, if the waiting sequence is within [0, M), M buckets can be allocated, and the I-th bucket records the occurrence of I. Finally, the data is output in an ordered form based on the position information received by each bucket. Here we use two temporary arrays, one for recording location information and one for facilitating the output of data in an ordered manner. Additionally, we assume that the data falls between 0 and MAX. If the given data does not start from 0, you can subtract the smallest number from each number

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
package algorithms;

public class BucketSorter {
	
 		public void sort(int[] keys,int from,int len,int max)     {         
 		int[] temp = new int[len];         
 		int[] count = new int[max];             
 		
 		for(int i=0;i<len;i++)         {             
 			count[keys[from+i]]++;         
 		}         
 		
 		//calculate position info         
 		for(int i=1; i<max; i++)         {             
 			count[i]=count[i]+count[i-1];//this means how many number which is less or equals than i,thus it is also position + 1          
 		}           
 		
 		System.arraycopy(keys, from, temp, 0, len);         
 		
 		for(int k=len-1; k>=0; k--)//from the ending to beginning can keep the stability         {             
 			keys[--count[temp[k]]] = temp[k];// position +1 =count         
 		}     
 	}     
 	  
 	
 	public static void main(String[] args) {           
 		int[] a= {1,4,8,3,2,9,5,0,7,6,9,10,9,13,14,15,11,12,17,16}; 
 		BucketSorter sorter=new BucketSorter();         
 		sorter.sort(a,0,a.length,20);//actually is 18, but 20 will also work 
 		for(int i=0; i<a.length; i++)         {            
			System.out.print(a[i]+",");         
		}       
	}  
 }

Nine cardinal sort can be said to be an extended bucket sort. For example, when the sequence to be sorted is within a large range, such as 0 to 999999, using bucket sort is a waste of space. And cardinality sorting breaks down each sorting code into d sorting codes, for example, any 6-digit number (padded with 0 before less than six digits) is broken down into 6 sorting codes, which are one digit, ten digit, one hundred digit…. When sorting, it is done in 6 steps, and each time it is sorted by the i-th sorting code. There are generally two ways:

*High Priority (MSD): Sort the sequence from high to low in sequence
*Low order priority (LSD): Sort the sequence from low to high order in sequence

Computers generally use low order priority (humans generally use high order priority), but when using low order priority, it is important to ensure the stability of the sorting algorithm. Cardinality sorting uses bucket sorting, and bucket sorting is used every time sorting by the Nth position. There are two ways to arrange the data that falls into the same bucket each time:

*Sequential storage: Use bucket sorting each time, put r buckets, and increase the count when they are the same.
*Chain storage: Each bucket is tracked through a static queue.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
 package algorithms;   
 
 import java.util.Arrays;
 
 public class RadixSorter {       
 	public static boolean USE_LINK=true;       
 	
   public void sort(int[] keys,int from ,int len,int radix, int d)     {  
          if(USE_LINK)         { 
              link_radix_sort(keys,from,len,radix,d);         
          } else {             
          	array_radix_sort(keys,from,len,radix,d);         
          }       
   }         
   
   
   private final void array_radix_sort(int[] keys, int from, int len, int radix,             int d)      {         
   		int[] temporary=new int[len];         
   		int[] count=new int[radix];         
   		int R=1;           
   		for(int i=0;i<d;i++)         {             
   			System.arraycopy(keys, from, temporary, 0, len);   
   			Arrays.fill(count, 0);             
   			for(int k=0;k<len;k++)             {              
   			   int subkey=(temporary[k]/R)%radix;             
   			   count[subkey]++;             
   			}            
   			
   		   for(int j=1;j<radix;j++)             {  
   		      count[j]=count[j]+count[j-1];             
   		   }             
   		   
   		   
   		   for(int m=len-1;m>=0;m--)             {                 
   		   		int subkey=(temporary[m]/R)%radix;                 
   		   		--count[subkey]; 
   		   		keys[from+count[subkey]]=temporary[m];             
   		   	}             
   		   	
   		   	R*=radix;        
		}      
	 }         
	 
	 private static class LinkQueue     {         
	 	int head=-1;         
	 	int tail=-1;     
	 }     
	 
	 private final void link_radix_sort(int[] keys, int from, int len, int radix, int d) {           
	 	int[] nexts=new int[len];           
	 	LinkQueue[] queues=new LinkQueue[radix];         
	 	
	 	for(int i=0;i<radix;i++)         {             
	 		queues[i]=new LinkQueue();         
	 	}         
	 	
	 	for(int i=0;i<len-1;i++)         {             
	 		nexts[i]=i+1;         
	 	}         
	 	
	 	nexts[len-1]=-1;           
	 	int first=0;         
	 	for(int i=0;i<d;i++)         { 
	 	            	link_radix_sort_distribute(keys,from,len,radix,i,nexts,queues,first);             		first=link_radix_sort_collect(keys,from,len,radix,i,nexts,queues);         }        
	 	            	
	 	            	
	 	 int[] tmps=new int[len];         
	 	 int k=0;         
	 	 while(first!=-1)         {              
	 	 	 tmps[k++]=keys[from+first];             
	 	 	 first=nexts[first];         
	 	 }         
	 	 
	 	 System.arraycopy(tmps, 0, keys, from, len);         
	}     
	
	
	private final void link_radix_sort_distribute(int[] keys, int from, int len,             int radix, int d, int[] nexts, LinkQueue[] queues,int first) {           
		for(int i=0;i<radix;i++)
			queues[i].head=queues[i].tail=-1;         
		
		while(first!=-1)         {            
			int val=keys[from+first];             
			for(int j=0;j<d;j++)val/=radix;             
			val=val%radix;             
			
			if(queues[val].head==-1)             {  
			    queues[val].head=first;             
			}  else {                 
				nexts[queues[val].tail]=first;               
			}             
			
			queues[val].tail=first;             
			first=nexts[first];         
		}       
	}     
	
	private int link_radix_sort_collect(int[] keys, int from, int len,             int radix, int d, int[] nexts, LinkQueue[] queues) {         
			int first=0;         
			int last=0;         
			int fromQueue=0;         
			for(;(fromQueue<radix-1)&&(queues[fromQueue].head==-1);fromQueue++);         
				first=queues[fromQueue].head;         				last=queues[fromQueue].tail;           				while(fromQueue<radix-1&&queues[fromQueue].head!=-1)         {  
				    fromQueue+=1;             
				    for(;(fromQueue<radix-1)&&(queues[fromQueue].head==-1);fromQueue++);               nexts[last]=queues[fromQueue].head;             
				    last=queues[fromQueue].tail;          
				     }         
				     
				     if(last!=-1)nexts[last]=-1;         
				     return first;     
				     
   }       
   
 	 public static void main(String[] args) {         
  			int[] a={1,4,8,3,2,9,5,0,7,6,9,10,9,135,14,15,11,222222222,1111111111,12,17,45,16};           USE_LINK=true;         
  			RadixSorter sorter=new RadixSorter();         
  			sorter.sort(a,0,a.length,10,10);         
  			for(int i=0;i<a.length;i++)         {    
  			         System.out.print(a[i]+",");         
  			}  
  			       
  		}   
}