Java direct insert sort example

The general impact of sorting efficiency from three aspects of comparison: the number of data comparison, the number of data movement, the size of the memory space occupied.
Let's do a general comparison of bubble sort, selection sort, insertion sort, and quicksort. Generally, bubble sort algorithm is not used, because it has the largest number of comparisons and moves among the sorting algorithms. Its only advantage is that the algorithm is simple and easy to understand, so it will have some application value when the amount of data is small. Selection sort, like bubble sort, is n squared in terms of number of comparisons, but it minimizes the number of exchanges, so selection sort can be applied when the amount of data is small and the exchange of data is more time-consuming than the comparison.
In most cases, the insertion sort algorithm is the best choice when the amount of data is small or basically ordered. Quicksort is often the best method for sorting larger amounts of data.
The sorting algorithm above occupies very little memory space and only requires an additional variable to temporarily store the data items during the exchange. So there is no comparability in the size of the memory footprint.

The number of comparisons for insertion sort is still n squared, but in general it's twice as fast as bubble sort, and a little bit faster than selection sort. It is often used in the final stages of complex sorting algorithms, such as quicksort.

Algorithm: after I -1 processing, L[1.. I -1] has been sorted. The I pass only inserts L[I] into the appropriate location of L[1.. I -1],
So that L[1.. I] is again the ordered sequence. To achieve this, we can use the sequential comparison method.
First compare L[I] with L[I -1], if L[I -1]< =L[I], then L[1..
Otherwise, exchange the positions of L[I] and L[i-1], and continue to compare L[i-1] and L[i-2] until a certain position j(1 Or less j Or less i-1) is found.
Until L[j] Or less L[j+1]
Advantages: less movement of elements, only one auxiliary space is needed
N times n
This is a good way to sort when the number of records to sort is small. But when n is large, it doesn't work

For example: int[] values = {5, 2, 4, 1, 3};

Sorting process:
The first time: 2,5,4,1,3
The second time: 2,4,5,1,3
The third time: 1,2,4,5,3
The fourth time: 1,2,3,4,5

Java code:

public class InsertSort {
   public static void main(String[] args) {
       int[] values = { 5, 2, 4, 1, 3 };
       sort(values);
       for (int i = 0; i < values.length; ++i) {
           System.out.println(values[i]);
       }
   }
   public static void sort(int[] values) {
       int temp;
       int j = 0;
       for (int i = 1; i < values.length; i++) {
           if(values[i]<values[i-1])//The judgment is important here, which shows why insertion sort is faster than bubble sort and selection sort.
           {
               temp = values[i];
               //Data moves back
               for (j=i-1; j>=0 && temp<values[j]; j--)
               {
                   values[j+1] =values[j];
               }
               //Insert the data into the j+1 position
               values[j+1] =temp;
               System.out.print(" The first " + (i + 1) + " Time: ");
               for (int k = 0; k < values.length; k++) {
                   System.out.print(values[k]+",");
               }
               System.out.println("");
           }
       }
   }
}

Second example

package cn.cqu.coce.xutao;
public class zhijiecharu {

 public static void main(String args[]){

 int a[]={1,2,34,67,8,9,6,7,56,34,232,99};
 int i,j,k;
 for(i=0;i<a.length;i++)
  System.out.print(a[i]+"t");
 System.out.println();
 for(i=1;i<a.length;i++){

  for(j=i-1;j>=0;j--)
   if(a[i]>a[j])
    break;

  if(j!=i-1){
   int temp;
   temp=a[i];
   for(k=i-1;k>j;k--)
    a[k+1]=a[k];
   a[k+1]=temp;  
  }  
 }
 for(i=0;i<a.length;i++)
  System.out.print(a[i]+"t");
 System.out.println();
  }
}

< img SRC = "border = 0 / / files.jb51.net/file_images/article/201405/20140507092556.jpg? 20144792846 ">