The Java sorting algorithm summarizes the insertion sort

This article illustrates the Java insertion sort method. Share with you for your reference. Specific analysis is as follows:

If you have an ordered data sequence, you need to insert a number into the ordered data sequence, but the data sequence is still ordered after the insertion. This article focuses on the Java implementation of insertion sort.
 
The basic operation of insertion sort is to insert a data into the ordered data that has already been sorted, so as to get a new ordered data with a number plus one. The time complexity of comparison and exchange is O(n^2), the algorithm is adaptive, for the data has been basically ordered, the time complexity is O(n), the algorithm is stable, the cost is very low. The algorithm is suitable for cases where the data has been basically ordered or the data volume is small.

The insertion algorithm divides the array into two parts: the first part contains all the elements of the array except the last element, and the second part contains only that element. After the first part is sorted, insert the last element into the place where the first part is now ordered.

Algorithm description

Generally, insertion sort is implemented on an array using in-place. The specific algorithm is described as follows:

1. Start with the first element, which can be considered sorted
2. Take the next element and scan it backwards and forwards in the sorted element sequence
3. If the element (sorted) is greater than the new element, move the element to the next position
4. Repeat step 3 until you find the position where the sorted element is less than or equal to the new element
5. Insert the new element into the next location
Repeat step 2

If the comparison operation is more expensive than the swap operation, binary search can be used to reduce the number of comparison operations. The algorithm can be considered as a variant of insertion sort, called binary search sort.

Code implementation

public void insertionSort() { 
  //Insertion sort
  int out, in; 
  int count1 = 0, count2 = 0;//Number of copies, number of comparisons
  for (out = 1; out < nElems; out++) { 
   long temp = a[out]; 
   in = out; 
   boolean flag=in>0&&a[in-1]>=temp; 
   while(flag){ 
   if(a[in-1]>=temp){ 
    if(in>0){ 
    a[in]=a[in-1]; 
    count1++; 
    --in;  
    } 
   } 
    count2++; 
    flag=in>0&&a[in-1]>=temp; 
   }  
   a[in] = temp; 
  } 
  System.out.println(" Number of replication: " + count1 + "  The number of comparisons is: " + count2); 
}

The insertion sort method is efficient when the data has a certain order. If the data is irregular, however, a large amount of data needs to be moved, which is just as inefficient as bubble sort and selection sort.

I hope this article has been helpful to your Java programming.