정렬을 직접 삽입하십시오
1 정렬 아이디어 :
정렬 할 레코드 RI는 이미 분류 된 레코드 R1, R2, ..., R (N-1)에 삽입됩니다.
두 번째 요소에서 시작하여 랜덤 시퀀스의 경우, 요소를 차례로 요소의 해당 위치에 삽입합니다. 정렬되기 전 요소.
첫 번째 순서 : 두 번째 요소를 앞의 순서로 주문한 목록에 삽입하십시오 (이 시점에서는 이전 요소에는 하나의 요소 만 있습니다. 물론 주문됩니다). 그 후,이 시퀀스의 처음 두 요소가 주문됩니다.
두 번째 정렬 : 첫 두 요소가 주문되도록 이전 길이 2의 주문 된 목록에 세 번째 요소를 삽입하십시오.
그리고 nth 요소가 이전 길이 (n-1)의 순서대로 목록에 삽입 될 때까지.
2 알고리즘 구현 :
// 직접 삽입 정렬 void straight_insert_sort (int num [], int len) {int i, j, key; for (j = 1; j <len; j ++) {key = num [j]; I = J-1; while (i> = 0 && num [i]> 키) {num [i+1] = num [i]; 나--; } num [i+1] = 키; }}3 성능 분석 :
3.1 공간 복잡성 : 위에서 언급했듯이 보조 장치 키가 사용되며 공간 복잡성은 O (1)입니다.
3.2 시간 복잡성 :
3.2.1 최상의 사례 : 정렬 할 레코드가 이미 주문되어 있으며 한 번에 정렬하고 키워드를 한 번 비교하고 레코드를 두 번 이동합니다. 전체 과정
비교 수는입니다
이동 레코드의 수는 다음과 같습니다
시간 복잡성 O (N)
3.2.2 최악의 경우 : 정렬 할 레코드는 이미 역 순서이며 키워드 비교 시간은 I (I-1에서 0에서), 레코드가 이동 (i+2) 시간입니다. 전체 과정
비교 수는입니다
이동 레코드의 수는 다음과 같습니다
시간 복잡성 o (n^2)
3.2.3 평균 시간 복잡성 : O (n^2)
3.3 안정성 : 안정
하프 삽입 정렬을 접습니다
1 정렬 아이디어 :
직접 분류에 기초하여, 정렬 된 레코드는 이미 분류 된 레코드 R1, R2, ..., R (N-1)에 삽입됩니다. 레코드 R1, R2, ..., R (N-1)이 정렬되었으므로 삽입 위치를 찾을 때 "하프 찾기"를 사용할 수 있습니다.
2 알고리즘 구현 :
// 접는 반 삽입 정렬 void binary_insert_sort (int num [], int len) {int i, j, 키, 낮음, 높음, 중간; for (i = 1; i <len; i ++) {key = num [i]; 낮음 = 0; 높음 = I-1; MID = (낮은+높음)/2; // 삽입 지점을 찾으십시오. 최종 삽입 지점은 낮으며 (낮음 <= high) {if (key <num [mid]) High = mid-1; else low = mid+1; MID = (낮은+높음)/2; } // (j = i; j> low; j-) {num [j] = num [j-1]; } // 레코드 숫자 삽입 [low] = key; }}3 성능 분석 :
3.1 공간 복잡성 : 위에서 언급했듯이 보조 장치 키가 사용되며 공간 복잡성은 O (1)입니다.
3.2 시간 복잡성 : 반 마감 검색이 레코드와 비교 수를 줄이지 만 움직임 수를 줄이지 않으므로 시간 복잡성은 직접 검색 알고리즘과 동일합니다.
3.2.1 최고의 사례 : 시간 복잡성 O (N)
3.2.2 최악의 경우 : 시간 복잡성 O (n^2)
3.2.3 평균 시간 복잡성 : O (n^2)
3.3 안정성 : 안정