java direct insertion sort example

The factors that affect sorting efficiency are generally compared from three aspects: the number of data comparisons, the number of data moves, and the size of the memory space occupied.
Let’s make a general comparison of bubble sort, selection sort, insertion sort, and quick sort. Bubble sorting algorithm is generally not used because its number of comparisons and moves is the largest among several sorting algorithms. Its only advantage is that the algorithm is simple and easy to understand, so it can be used when the amount of data is small. There will be some application value. Selection sort has the same number of comparisons as bubble sort, which is n squared, but it reduces the number of exchanges to a minimum, so it can be applied when the amount of data is small and exchanging data is more time-consuming than comparing data. Select sort.
In most cases, when the amount of data is relatively small or basically ordered, the insertion sort algorithm is the best choice. For sorting larger amounts of data, quicksort is usually the best method.
The above sorting algorithm takes up very little memory space and only requires an additional variable to temporarily store the data items during exchange. Therefore, there is no comparison in the size of the memory space occupied.

The number of comparisons of insertion sort is still n squared, but in general, it is twice as fast as bubble sort and a little 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-th pass only inserts L[i] into the appropriate position of L[1..i-1],
making L[1..i] a sorted sequence again. To achieve this goal, we can use sequential comparison.
First compare L[i] and L[i-1]. If L[i-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≤j≤i -1),
Until L[j] ≤ L[j+1]
Advantages: Less number of moving elements, only one auxiliary space is needed
Time complexity n*n
When waiting This is a good sorting method when the number of sorted records n is small. But when n is very large, it is not suitable

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

Sort process:
1st time: 2 ,5,4,1,3
The 2nd time: 2,4,5,1,3
The 3rd time: 1,2,4,5,3
The 4th 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])//此处的判断很重要，这里体现了插入排序比冒泡排序和选择排序快的原因。
           {
               temp = values[i];
               //数据往后移动
               for (j=i-1; j>=0 && temp<values[j]; j--)
               {
                   values[j+1] =values[j];
               }
               //将数据插入到j+1位置
               values[j+1] =temp;
               System.out.print("第" + (i + 1) + "次：");
               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();
  }
}

For more java direct insertion sorting examples and related articles, please pay attention to the PHP Chinese website!