Simple example of Java insertion sort

This article mainly introduces Java simple insertion sorting examples in detail, which has certain reference value. Interested friends can refer to it

1. Basic concepts

The basic operation of insertion sort is to insert a data into the ordered data that has been sorted, so as to obtain a new ordered data with the number plus one. The algorithm is suitable for sorting a small amount of data, and the time The complexity is O(n^2). It is a stable sorting method. The insertion algorithm divides the array to be sorted into two parts: the first part contains all the elements of the array, except for the last element (making the array one more space to have an insertion position), and the second part only contains this one element (i.e. the element to be inserted). After the first part is sorted, this last element is inserted into the sorted first part.

2. Java code implementation

public class InsertSort {
  public static void inserSort(int[] array){
    if (array==null||array.length<2){
      return;
    }

    for (int i=1;i<array.length;i++){ //默认第一个元素为有序队列，从第二个元素开始循环插入
      int position=array[i];     //设置第二个元素为要插入的数据
      int j=i-1;
      while (j>=0&&position<array[j]){
        array[j+1]=array[j];   //如果插入发数小于第j个元素，将第j个数向后移
        j--;
      }
      array[j+1]=position;     //插入
    }
  }

  public static void main(String ags[]){
    int[] array={2,6,4,7,3,-1};
    inserSort(array);
    for (int i=0;i<array.length;i++){
      System.out.print(array[i]+" ");
    }
  }
}

3. Performance analysis

Stable
Space complexity O(1)
Time complexity O(n2)
Worst case: reverse order, need to move n*(n-1)/2 elements
Best case: Positive order, no need to move elements

The above is the detailed content of Simple example of Java insertion sort. For more information, please follow other related articles on the PHP Chinese website!