[데이터 구조의 정렬 2] 정렬 을 직접 삽입 합 니 다.

정렬 (Insertion Sort) 을 삽입 하 는 기본 사상 은 정렬 할 기록 을 매번 키워드 크기 에 따라 앞 에 정렬 된 하위 파일 의 적당 한 위치 에 삽입 하고 모든 기록 이 완 료 될 때 까지 삽입 하 는 것 입 니 다.이 절 은 첫 번 째 정렬 방법 을 소개 합 니 다. 정렬 을 직접 삽입 합 니 다.
정렬 기본 사상 직접 삽입
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 [1. i - 1] 에 기 록 된 모든 키워드 보다 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. 정렬 안정성 직접 삽입
    정렬 을 직접 삽입 하 는 것 은 안정 적 인 정렬 방법 이다.
원본 주소:http://student.zjzk.cn/course_ware/data_structure/web/main.htm