직접 삽입 정렬
정렬을 직접 삽입한다는 아이디어는 이해하기 쉽습니다.
1. 배열을 분류 및 분류되지 않은 두 부분으로 분류하십시오. 처음에는 첫 번째 요소가 정렬되는 것으로 간주됩니다.
2. 두 번째 요소부터 시작하여 정렬 된 서브 어레이에서 요소의 적절한 위치를 찾아 삽입하십시오.
3. 마지막 요소가 정렬 된 서브 어레이에 삽입 될 때까지 위의 프로세스를 반복하십시오.
4. 정렬이 완료되었습니다.
예:
아이디어는 간단하지만 코드는 버블 분류만큼 쓰기가 쉽지 않습니다. 우선, 올바른 위치를 결정하는 방법? 왼쪽보다 크거나 동일하며 오른쪽보다 작거나 동일합니까? 아니요, 많은 경계 조건을 고려해야하며 판단이 너무 많습니다. 둘째, 요소를 배열에 삽입하려면 필연적으로 많은 수의 요소를 움직여야합니다. 그들의 움직임을 통제하는 방법?
실제로 이것은 알고리즘 자체에 문제가되지 않으며 프로그래밍 언어와 관련이 있습니다. 때로는 알고리즘 자체가 이미 매우 성숙하며 특정 프로그래밍 언어와 관련하여 여전히 약간 변경해야합니다. 여기서 우리가 말하는 것은 Java 알고리즘이므로 Java에 대해 이야기합시다.
위의 문제를 해결하기 위해 두 번째 단계를 약간 개선했습니다. 우리는 서브 어레이의 시작 위치에서 비교를 시작하지 않지만 서브 어레이의 꼬리에서 역 비교를 시작합니다. 삽입 해야하는 숫자보다 크면 뒤로 이동합니다. 숫자가 숫자보다 크지 않을 때까지 삽입 할 숫자는이 빈 위치에 배치됩니다. 따라서 다음 코드를 작성할 수 있습니다.
insertarray.java
공개 클래스 insertArray {// array private long [] arr; // 배열의 유효한 데이터의 크기는 개인 int elems; // 기본 생성자 public insertArray () {arr = new Long [50]; } public insertArray (int max) {arr = new long [max]; } // 데이터 삽입 데이터 공개 void insert (long value) {arr [elems] = value; Elems ++; } // 데이터 표시 공개 void display () {for (int i = 0; i <elems; i ++) {system.out.print (arr [i]+""); } system.out.println (); } // sort 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] = 선택; }}} 테스트 클래스 :
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)입니다.
평균 상황 : 위의 분석에서, 우리는 평균 상황에서 알고리즘의 작동 수가 대략 (n^2)/2임을 얻을 수 있습니다 (참고 : 여기 계산은 할당과 비교를 기반으로합니다. 움직임과 비교를 기반으로하는 경우 대략 n^2/4). 분명히, 시간 복잡성은 여전히 O (n^2)입니다.
알고리즘의 공간 복잡성에 대해서는 모든 움직임이 데이터 내부에서 수행됩니다. 유일한 오버 헤드는 우리가 임시 변수를 도입했다는 것입니다 (일부 데이터 구조는 책에서 "센티넬"이라고 함)이므로 공간적 복잡성 (추가 공간)은 O (1)입니다.
알고리즘 안정성
현재 숫자보다 크지 않고 교체 할 필요가없는 위치 만 찾아야하므로 정렬을 직접 삽입하는 것은 안정적인 정렬 방법입니다.
알고리즘 변형
배열해야 할 데이터가 많으면 뒤에서 앞뒤로 볼 때마다 많은 오버 헤드가 발생합니다. 검색 속도를 향상시키기 위해 바이너리 검색을 사용하여 성능 최적화에 사용할 수 있습니다. 이진 검색의 효율이 매우 높기 때문에 O (N) 복잡성이 보장되며 더 많은 데이터가 있거나 입력 데이터가 최악의 경향이있을 때 검색 효율이 크게 향상 될 수 있습니다. 일부 책에서는이 방법을 폴딩 및 하프 삽입 분류라고합니다. 코드 구현은 상당히 복잡하며 앞으로 시간이 있으면 게시 할 수 있습니다.
또한 2 방향 삽입 정렬 및 테이블 인서트 정렬이 있습니다. 접이식 및 반 삽입 정렬에 따라 2 방향 삽입 정렬이 더욱 향상되고 N^2/8 정도의 움직임 수가 크게 줄어 듭니다. 그러나 움직임의 수를 피하지 않으며 복잡성 수준을 줄이지 않습니다. 테이블 삽입 정렬은 스토리지 구조를 완전히 변경하고 레코드를 이동하지 않지만 링크 된 목록을 유지해야하며 링크 된 목록의 포인터는 이동 레코드 대신 수정됩니다. 따라서 복잡성은 여전히 O (n^2)입니다.
양방향 삽입 정렬 및 테이블 삽입 정렬의 경우 Yan Weimin과 Wu Weimin이 편집 한 "데이터 구조"를 참조하십시오.
알고리즘 적용 가능한 시나리오
O (n^2)의 복잡성으로 인해 배열이 큰 경우 삽입 분류가 적용되지 않습니다. 그러나 데이터가 상대적으로 적을 때는 일반적으로 빠른 정렬을위한 확장으로 사용되는 좋은 선택입니다. 예를 들어, STL의 정렬 알고리즘 및 stdlib의 QSORT 알고리즘에서 삽입 분류는 빠른 분류의 보충제로 사용되며 소수의 요소를 정렬하는 데 사용됩니다. 예를 들어, jdk 7 java.util.arrays에 사용 된 정렬 방법의 구현에서 정렬 할 배열의 길이가 47 미만인 경우 삽입 분류가 사용됩니다.