정렬 기본 사상 직접 삽입

정렬 기본 사상 직접 삽입 1. 기본 사상    정렬 할 기록 이 배열 R [1. n] 에 저장 된다 고 가정 합 니 다.초기 에 R [1] 은 1 개의 질서 있 는 구역 을 만 들 었 고 무질서 한 구역 은 R [2. n] 이 었 다.i = 2 부터 i = n 까지 순서대로 R [i] 를 현재 질서 구역 R [1. i - 1] 에 삽입 하여 n 개의 기록 을 포함 하 는 질서 구역 을 생 성 합 니 다.2. i - 1 번 째 정렬 삽입:    보통 하나의 기록 R [i] (i = 2, 3,..., n - 1) 을 현재 의 질서 구역 에 삽입 하여 삽입 한 후에 도 이 구간 의 기록 을 키워드 에 따라 질서 있 게 조작 하 는 것 을 i - 1 번 직접 삽입 정렬 이 라 고 합 니 다.    정렬 과정의 어느 중간 에 R 은 두 개의 하위 구간 R [1. i - 1] (정렬 된 질서 구역) 과 R [i. n] (현재 정렬 되 지 않 은 부분, 무질서 구역 이 라 고 할 수 있 음) 으로 나 뉜 다.    정렬 을 직접 삽입 하 는 기본 동작 은 현재 무질서 구역 의 첫 번 째 기록 인 R [i] 를 질서 구역 R [1. i - 1] 의 적당 한 위치 에 삽입 하여 R [1. i] 를 새로운 질서 구역 으로 바 꾸 는 것 입 니 다.이 방법 은 매번 질서 있 는 구역 에 기록 을 1 개 씩 늘 리 기 때문에 보통 증분 법 이 라 고 부른다.    정렬 을 삽입 하 는 것 은 포커 를 칠 때 손 에 있 는 카드 를 정리 하 는 것 과 매우 유사 하 다.만 져 온 첫 번 째 카드 는 정리 할 필요 가 없 으 며, 이후 매번 책상 위의 카드 (무질서 구역) 에서 맨 위 에 있 는 1 장 을 만 지고 왼손 의 카드 (질서 구역) 의 정확 한 위치 에 삽입 된다.이 정확 한 위 치 를 찾기 위해 서 는 왼쪽 에서 오른쪽으로 (또는 오른쪽 에서 왼쪽으로) 만 져 온 패 와 왼손 에 있 는 패 를 하나씩 비교 해 야 한다.정렬 방법 1. 간단 한 방법    먼저 현재 질서 구역 R [1. i - 1] 에서 R [i] 의 정확 한 삽입 위치 k (1 ≤ k ≤ i - 1) 를 찾 습 니 다.그리고 R [k. i - 1] 의 기록 을 모두 한 위치 로 옮 기 고 k 위치 에 있 는 공간 을 내 어 R [i] 에 삽입 합 니 다.  주의:    R [i] 의 키워드 가 R [1. i - 1] 에 기 록 된 모든 키워드 보다 크 면 R [i] 는 원래 위치 에 삽입 하 는 것 이다.2. 개선 하 는 방법 은 비교 조작 과 기록 이동 조작 을 교체 적 으로 진행 하 는 방법 을 찾 는 것 이다.구체 적 인 방법:    기록 R [i] 을 삽입 할 키 워드 를 오른쪽 에서 왼쪽으로 순서대로 질서 구역 에 R [j] (j = i - 1, i - 2,..., 1) 키 워드 를 기록 하여 비교 합 니 다.    ① R [j] 의 키워드 가 R [i] 의 키워드 보다 크 면 R [j] 를 한 위치 로 옮 깁 니 다.      ② R [j] 의 키워드 가 R [i] 의 키워드 보다 작 거나 같 으 면 검색 과정 이 끝나 고 j + 1 은 R [i] 의 삽입 위치 입 니 다.    키워드 가 R [i] 의 키워드 보다 큰 기록 이 모두 뒤로 이동 되 었 기 때문에 j + 1 의 위 치 는 이미 비어 있 습 니 다. R [i] 를 이 위치 에 직접 삽입 하면 정렬 을 직접 삽입 할 수 있 습 니 다.정렬 알고리즘 직접 삽입 1. 알고리즘 설명  void lnsertSort(SeqList R)    {/ / 순서 표 R 의 기록 R [1. n] 을 증가 순서에 따라 삽입 정렬 합 니 다.    int i，j；     for (i = 2; i < = n; i + +) / / R [2],..., R [n] 순서대로 삽입      if (R [i]. key < R [i - 1]. key) {/ R [i]. key 가 질서 있 는 구역 의 모든 keys 보다 크 면 R [i]                              //원래 의 위치 에 있어 야 한다.        R [0] = R [i]; j = i - 1; / R [0] 은 보초병 이 고 R [i] 의 사본 이다.        do {/ / 오른쪽 에서 왼쪽으로 질서 있 는 구역 R [1. i - 1] 에서 R [i] 의 삽입 위 치 를 찾 습 니 다.         R [j + 1] = R [j]; / 키 워드 를 R [i]. key 의 기록 보다 크게 이동         j-- ；          }while (R [0]. key < R [j]. key); / / R [i]. key ≥ R [j]. key 시 종료        R [j + 1] = R [0]; / / R [i] 을 올 바른 위치 에 삽입       }//endif    }//InsertSort 
2. 보초병 의 역할    알고리즘 에 도 입 된 추가 기록 R [0] 을 감시초 나 보초병 (Sentinel) 이 라 고 한다.   보초병 은 두 가지 역할 을 한다. ① 사람 이 찾기 (위치 삽입) 순환 하기 전에 R [i] 의 사본 을 저장 하여 기록 후 이동 으로 인해 R [i] 의 내용 을 잃 어 버 리 지 않도록 한다. ② 그 주요 역할 은 찾기 순환 에서 '감시' 하 표 변수 j 가 경 계 를 넘 었 는 지 여부 이다. 일단 경 계 를 넘 으 면 (즉 j = 0) R [0] 때문이다.. key 와 자신 을 비교 하면 순환 판정 조건 이 성립 되 지 않 아 검색 순환 이 끝나 고 이 순환 에서 매번 j 가 경 계 를 넘 었 는 지 확인 하 는 것 을 피 할 수 있 습 니 다 (즉, 순환 판정 조건 인 'j > = 1' 을 생략 합 니 다).  주의:  ① 실제로 모든 경계 조건 을 간소화 하기 위해 도입 한 부가 결점 (요소) 은 보초병 이 라 고 할 수 있다.  【 예 】싱글 체인 시트 의 두 결점 은 사실상 보초병 ② 보초병 을 도입 한 후 순환 조건 을 찾 는 시간 을 절반 가량 줄 였 기 때문에 기록 수가 많은 파일 에 대한 절약 시간 이 상당 하 다. 정렬 과 같은 사용 빈도 가 매우 높 은 계산법 에 대해 서 는 운행 시간 을 최대한 줄 여야 한다. 따라서 상기 알고리즘 중의 보초병 을 볼 수 없다.작은 기술 을 위해 서 는 이러한 기 교 를 깊이 이해 하고 파악 해 야 합 니 다. 인 스 턴 스 를 입력 하 는 정렬 과정 을 지정 합 니 다.    정렬 을 기다 리 는 파일 은 8 개의 기록 이 있 습 니 다. 그 키 워드 는 각각 49, 38, 65, 97, 76, 13, 27, 49 입 니 다. 두 개의 똑 같은 키 워드 를 구별 하기 위해 49, 그 다음 49 의 아래 에 선 을 그 어 차 이 를 보 여 주 었 습 니 다. 그 정렬 과정 은 [애니메이션 시 뮬 레이 션] 알고리즘 분석 1. 산법 의 시간 성능 분석 을 볼 수 있 습 니 다.      n 개의 기록 이 있 는 파일 에 대해 n - 1 번 정렬 을 해 야 합 니 다.    각종 상태 에서 의 시간 복잡 도: 9484 ° - - - 9516 ° - - 9516 ° - - 9516 ° - - 9516 ° - - - 9488 ° ☆ 초기 파일 상태     │   정상 적 인 순서   │     역순   ☆ 무질서 (평균)  ☆ ├ -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- ┤ ☆ 제 i 의 열쇠      │   1      │     i+1    │ （i-2）/2  ☆ ☆ 글자 비교 횟수       │          │            │            ☆ ├ -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- ┤ 전체 키워드 비교 횟수  │   n-1    │(n+2)(n-1)/2│ ≈n2/4     ☆ ├ -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- ┤ ☆ 첫 번 째 이동 횟수 기록 ☆   0      │ i+2        │ （i-2）/2  ☆ ├ -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- ┤ 전체 이동 횟수 기록  │   0      │(n-1)(n+4)/2│ ≈n2/4     ☆ -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 시간 복잡 도        │  0（n）  │ O（n2）    │ O（n2）    ☆ └ -- -- -- -- ┴ -- -- ┴ -- -- -- ┴ -- -- -- -- ┘ 주의:    초기 파일 은 키워드 에 따라 질서 가 있 고 '정렬' 이 라 고 약칭 합 니 다.    초기 파일 은 키워드 에 따라 순차 적 으로 줄 이 고 '역순' 이 라 고 부 릅 니 다. 2. 알고리즘 의 공간 복잡 도 분석    알고리즘 에 필요 한 보조 공간 은 감시초 소 입 니 다. 보조 공간 복잡 도 S (n) = O (1) 입 니 다. 현지 정렬 입 니 다. 3. 정렬 안정성 을 직접 삽입 합 니 다.    정렬 을 직접 삽입 하 는 것 은 안정 적 인 정렬 방법 이다. 
 
자신 이 쓴 간단 한 정렬 코드 삽입:
 

#include<stdio.h>
void main(){
	int a[10];//={9,8,7,6,5,4,3,2,1,0}
	int i,j,k,temp;
	printf("please input 10 num(n<100):
");
	for(i=0;i<10;i++)
		scanf("%d",&a[i]);
	for(i=1;i<10;i++){
		temp=a[i];
		for(j=0;j<i;j++){
			if(temp<a[j]){
				for(k=i-1;k>=j;k--){
					a[k+1]=a[k];
				}
				a[j]=temp;
				break;
			}
		}
	}
	for(i=0;i<10;i++){
		printf("%d ",a[i]);
	}
	printf("
");
}