Java 삽입 정렬의 간단한 예

이 글에서는 주로 참고할만한 Java 단순 삽입 정렬 예제를 자세히 소개합니다. 관심 있는 친구들은 참고해 보세요.

1. 기본 개념

삽입 정렬의 기본 동작은 정렬된 데이터에 Insert를 넣는 것입니다. 정렬된 데이터에 1을 더한 새로운 정렬된 데이터를 얻는 알고리즘은 적은 양의 데이터를 정렬하는 데 적합하며 시간 복잡도는 O(n^2)입니다. 안정적인 정렬 방법입니다. 삽입 알고리즘은 정렬할 배열을 두 부분으로 나눕니다. 첫 번째 부분에는 마지막 요소를 제외한 배열의 모든 요소가 포함되며(배열에 삽입 위치를 확보할 수 있는 공간이 하나 더 추가됨) 두 번째 부분에는 이 요소만 포함됩니다. 요소(즉, 삽입할 요소)입니다. 첫 번째 부분이 정렬된 후 이 마지막 요소가 정렬된 첫 번째 부분에 삽입됩니다.

2. Java 코드 구현

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. 성능 분석

Stable
공간 복잡도 O(1)
시간 복잡도 O(n2)
최악의 경우: 역순, n 이동 필요* (n-1)/2 요소
최고의 경우: 양수 순서, 요소를 이동할 필요가 없음

위 내용은 Java 삽입 정렬의 간단한 예의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!