직접 삽입 정렬 알고리즘 및 관련 Java 버전 코드 구현에 대한 자세한 설명

직접 삽입 정렬

직접 삽입 정렬의 개념은 다음과 같습니다.
1. 정렬할 배열을 정렬된 부분과 정렬되지 않은 부분으로 나눕니다. 첫 번째 An 요소는 정렬된 것으로 간주됩니다.
2. 두 번째 요소부터 시작하여 정렬된 하위 배열에서 요소의 적절한 위치를 찾아 해당 위치에 삽입합니다.
3. 순서가 지정된 하위 배열에 마지막 요소가 삽입될 때까지 위 과정을 반복합니다.
4. 정렬이 완료되었습니다.

예:
아이디어는 매우 간단하지만 코드 작성은 버블 정렬만큼 쉽지 않습니다. 첫째, 적절한 위치를 어떻게 결정합니까? 왼쪽보다 크거나 같나요, 오른쪽보다 작거나 같나요? 아니요, 고려해야 할 경계 조건도 많고 판단도 너무 많습니다. 둘째, 배열에 요소를 삽입하려면 필연적으로 많은 수의 요소를 이동해야 합니다. 이동을 제어하는 ​​방법은 무엇입니까?
사실 이는 알고리즘 자체의 문제는 아니고 프로그래밍 언어와 관련이 있습니다. 때로는 알고리즘 자체가 이미 매우 성숙하여 특정 프로그래밍 언어와 관련하여 약간 수정해야 하는 경우도 있습니다. 여기서 말하는 것은 Java 알고리즘이므로 Java에 대해 이야기해 보겠습니다.
위 문제를 해결하기 위해 두 번째 단계를 약간 개선하여 하위 배열의 시작 위치부터 비교를 시작하지 않고 하위 배열의 끝부터 역순으로 비교를 시작합니다. 삽입해야 할 숫자보다 크면 뒤로 이동합니다. 숫자가 이 숫자보다 크지 않을 때까지 삽입해야 하는 숫자가 이 빈 위치에 배치됩니다. 따라서 다음 코드를 작성할 수 있습니다.
InsertArray.java

public class InsertArray {
  // 数组
  private long[] arr;
 
  // 数组中有效数据的大小
  private int elems;
 
  // 默认构造函数
  public InsertArray() {
    arr = new long[50];
  }
 
  public InsertArray(int max) {
    arr = new long[max];
  }
 
  // 插入数据
  public void insert(long value) {
    arr[elems] = value;
    elems++;
  }
 
  // 显示数据
  public void display() {
    for (int i = 0; i < elems; i++) {
      System.out.print(arr[i] + " ");
    }
    System.out.println();
  }
 
  // 插入排序
  public void insertSort() {
    long select = 0L;
    for(int i = 1; i < elems; i++) {
      select = arr[i];
      int j = 0;
      for(j = i;j > 0 && arr[j - 1] >= select; j--) {
        arr[j] = arr[j - 1];
      }
      arr[j] = select;
    }
  }
}

테스트 클래스:
TestInsertArray.java

public class TestInsertArray {
  public static void main(String[] args) {
    InsertArray iArr = new InsertArray();
    iArr.insert(85);
    iArr.insert(7856);
    iArr.insert(12);
    iArr.insert(8);
    iArr.insert(5);
    iArr.insert(56);
 
    iArr.display();
    iArr.insertSort();
    iArr.display();
  }
 
}

알고리즘 성능/복잡성
직접 논의해 보겠습니다. 삽입 알고리즘의 복잡성. 입력에 관계없이 알고리즘은 항상 n-1 라운드의 정렬을 수행합니다. 그러나 각 요소의 삽입 위치가 불확실하고 입력 데이터의 영향을 많이 받기 때문에 그 복잡도는 확실하지 않습니다. 우리는 최선의 상황, 최악의 상황, 평균적인 상황에 대해 논의할 수 있습니다.
1. 최선의 경우: 알고리즘의 특성상 정렬되는 배열 자체가 양의 순서(배열이 순서대로 되어 있고 그 순서가 요구되는 순서와 동일할 때)가 가장 좋다고 볼 수 있습니다. , 이는 논의의 전제에 따른 오름차순입니다. 그 이유는 이 경우 각 요소를 한 번만 비교하면 되고 이동할 필요가 없기 때문입니다. 알고리즘의 시간 복잡도는 O(n);
2입니다. 최악의 경우: 분명히 정렬할 배열이 역순인 경우입니다. 이 경우 각 라운드의 비교 횟수는 i입니다. -1, 할당 개수는 i 입니다. 전체 차수는 계열 2n-1의 첫 번째 n 항의 합, 즉 n^2입니다. 알고리즘의 시간 복잡도는 O(n^2)입니다.
3. 분석을 통해 평균 사례 알고리즘을 얻을 수 있습니다. 작업 수는 대략 (n^2)/2입니다. (참고: 여기서 계산은 할당 및 비교를 기반으로 합니다. 이동 및 비교를 기반으로 하는 경우 약 n^2입니다. /4) 분명히 시간 복잡도는 여전히 O(n^2 )입니다.
알고리즘의 공간 복잡도와 관련하여 모든 이동은 데이터 내에서 수행됩니다. 유일한 오버헤드는 임시 변수(일부 데이터 구조 서적에서는 "센티넬"이라고 함)를 도입한다는 것입니다. 따라서 공간 복잡도(추가 공간) O(1)이다.

알고리즘 안정성
현재 개수보다 크지 않은 위치만 찾고 교환할 필요도 없기 때문에 직접 삽입 정렬이 안정적인 정렬 방법입니다.

알고리즘 변형
정렬할 데이터가 많은 경우 매번 뒤에서 앞으로 검색하면 오버헤드가 많이 발생하므로 이진 검색(이진 검색)을 사용합니다. )를 사용하여 성능을 향상할 수 있습니다. 이진 검색은 매우 효율적이고 O(㏒n) 복잡도를 보장하기 때문에 데이터가 많거나 입력 데이터가 최악의 경우에 검색 효율성을 크게 향상시킬 수 있습니다. 이 방법을 일부 책에서는 반삽입 정렬이라고 합니다. 코드 구현은 상대적으로 복잡하므로 나중에 시간이 나면 게시하겠습니다.
그 밖에도 양방향 삽입 정렬과 테이블 삽입 정렬이 있습니다. 양방향 삽입 정렬은 반 삽입 정렬을 기반으로 더욱 개선되었으며 이동 횟수가 약 n^2/8로 크게 줄어듭니다. 그러나 이동 횟수를 제거하거나 복잡성 수준을 낮추지는 않습니다. 테이블 삽입 정렬은 저장 구조를 완전히 변경하고 레코드를 이동하지 않지만 연결 목록을 유지하고 이동 레코드를 연결 목록의 포인터 수정으로 교체해야 합니다. 따라서 복잡도는 여전히 O(n^2)입니다.
양방향 삽입 정렬과 테이블 삽입 정렬은 Yan Weimin과 Wu Weimin이 편집한 책 "데이터 구조"를 참조하세요.

알고리즘 적용 시나리오
O(n^2)의 복잡성으로 인해 배열이 큰 경우 삽입 정렬을 적용할 수 없습니다. 하지만 데이터의 양이 상대적으로 적을 때 좋은 선택이며, 일반적으로 퀵 정렬의 확장으로 사용됩니다. 예를 들어 STL의 정렬 알고리즘과 stdlib의 qsort 알고리즘에서는 삽입 정렬이 퀵 정렬의 보완 수단으로 사용되어 적은 수의 요소를 정렬합니다. 또 다른 예로 JDK 7 java.util.Arrays에서 사용하는 정렬 메소드 구현 시 정렬할 배열의 길이가 47보다 작을 경우 삽입 정렬을 사용하게 된다.

직접 삽입 정렬 알고리즘에 대한 자세한 설명과 관련 Java 버전 코드 구현 관련 글은 PHP 중국어 홈페이지를 주목해주세요!