[데이터 구조의 정렬 3] 힐 정렬

이 절 은 두 번 째 삽입 정렬 방법 인 힐 정렬 을 소개 합 니 다.
힐 정렬 (Shell Sort) 은 정렬 을 삽입 하 는 일종 이다.D. L. Shell 이 1959 년 에 제기 하여 이름 을 얻 었 다.
힐 정렬 기본 사상
기본 사상: n 보다 작은 정수 d1 을 첫 번 째 증 량 으로 하고 파일 의 모든 기록 을 d1 개 조로 나눈다.모든 거리 가 d1 인 배수 의 기록 은 같은 그룹 에 놓 여 있다.먼저 각 그룹 내 에서 직접 삽입 정렬 하기;그 다음 에 두 번 째 증 량 d2 < d1 을 취하 여 상기 그룹 과 정렬 을 반복 합 니 다. 취 하 는 증 량 dt = 1 (dt < dt - 1 <... < d2 < d1), 즉 모든 기록 을 같은 그룹 에 놓 고 정렬 을 직접 삽입 할 때 까지 합 니 다.이 방법 은 실질 적 으로 그룹 삽입 방법 이다.
주어진 인 스 턴 스 셸 정렬 과정
정렬 대기 파일 에 10 개의 기록 이 있다 고 가정 하면 그 키 워드 는 49, 38, 65, 97, 76, 13, 27, 49, 55, 04 이다.증분 시퀀스 의 수 치 는 다음 과 같다. 5, 3, 1 정렬 과정, 예 를 들 어 [애니메이션 시 뮬 레이 션].
Shell 정렬 알고리즘 구현
1. 감시초 소 를 설치 하지 않 은 알고리즘 설명

  void ShellPass(SeqList R，int d)
   {//          ，d     
     for(i=d+1;i<=n；i++) // R[d+1．．n]            
       if(R[i].key<R[i-d].key){
         R[0]=R[i];j=i-d； //R[0]      ，    
         do {//  R[i]     
            R[j+d]；=R[j]； //    
            j=j-d； //      
         }while(j>0&&R[0].key<R[j].key)；
         R[j+d]=R[0]； //  R[i]       
       } //endif
   } //ShellPass


  void  ShellSort(SeqList R)
   {
    int increment=n； //    ，   n>0
    do {
          increment=increment/3+1； //     
          ShellPass(R，increment)； //     increment Shell    
       }while(increment>1)
    } //ShellSort

주의: 증 량 d = 1 시 ShellPass 와 InsertSort 는 기본적으로 일치 합 니 다. 다만 보초병 이 없 기 때문에 내부 순환 에 순환 판정 조건 인 'j > 0' 을 추가 하여 아래 표 가 경 계 를 넘 지 않도록 합 니 다.
2. 감시초 소 를 설치 한 셸 정렬 알고리즘
구체 적 인 산법 약.
알고리즘 분석
1. 증분 시퀀스 선택
셸 정렬 의 실행 시간 은 증분 시퀀스 에 의존 합 니 다.좋 은 증 량 서열 의 공 통 된 특징: ① 마지막 증 가 는 반드시 1 이 어야 한다.② 서열 중의 값 (특히 인접 한 값) 이 서로 배수 가 되 는 상황 을 피해 야 한다.어떤 사람 은 대량의 실험 을 통 해 현재 비교적 좋 은 결 과 를 제시 했다. n 이 비교적 클 때 비교 와 이동 횟수 는 약 n1.25 에서 1.6n 1.25 사이 이다.
2. Shell 정렬 의 시간 성능 은 정렬 을 직접 삽입 하 는 것 보다 좋 습 니 다.
힐 정렬 의 시간 성능 이 정렬 을 직접 삽입 하 는 것 보다 좋 은 이 유 는 ① 파일 의 초기 상태 가 기본적으로 질서 가 있 을 때 정렬 을 직접 삽입 하 는 데 필요 한 비교 와 이동 횟수 가 비교적 적다.② n 값 이 시간 에 비해 n 과 n2 의 차이 도 비교적 적다. 즉, 정렬 을 직접 삽입 하 는 가장 좋 은 시간 복잡 도 O (n) 와 최 악의 시간 복잡 도 0 (n2) 의 차이 가 크 지 않다.③ 힐 정렬 을 시작 할 때 증 가 량 이 많 고 그룹 이 많 으 며 각 그룹의 기록 수량 이 적 기 때문에 각 그룹 에 직접 삽입 하 는 것 이 빠 르 고 나중에 증 가 된 di 가 점점 줄 어 들 며 그룹 수 는 점점 줄 어 들 었 으 며 각 그룹의 기록 수량 은 점점 증가 했다. 그러나 di - 1 을 거리 로 배열 하여 파일 이 질서 있 는 상태 에 가 까 워 졌 기 때문에 새로운 정렬 과정 도 비교적 빠르다.따라서 힐 의 순 서 는 효율 적 으로 직접 삽입 하 는 것 보다 개선 되 었 다.
3. 안정성
힐 의 순 서 는 불안정 하 다.상기 사례 를 참조 하여 이 예 에서 두 개의 같은 키워드 49 는 정렬 전후의 상대 적 인 순서 에 변화 가 생 겼 다.
원본 주소:http://student.zjzk.cn/course_ware/data_structure/web/main.htm