데이터 구조 - 힐 정렬

힐 정렬 (Shell Sort) 은 정렬 을 삽입 하 는 일종 이다.D. L. Shell 이 1959 년 에 제기 하여 이름 을 얻 었 다.
힐 정렬 기본 사상
  기본 사상:
　    n 보다 작은 정수 d1 을 첫 번 째 증분 으로 하고 파일 의 모든 기록 을 d1 그룹 으로 나 눕 니 다.모든 거 리 는 dl 의 배수 로 같은 그룹 에 기록 되 어 있 습 니 다.먼저 각 그룹 내 에서 직접 삽입 정렬 하기;그 다음 에 두 번 째 증 량 d2 < d1 을 취하 여 상기 그룹 과 정렬 을 반복 합 니 다. 취 하 는 증 량 dt = 1 (dt < dt - l <... < 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 시 셸 패스 와 인 서 트 소 트 는 기본적으로 일치 하지만 보초병 이 없어 서 내 순환 에 순환 판정 조건 인 'j > 0' 을 추가 하여 아래 표 가 경 계 를 넘 지 않도록 한다.
2. 감시초 소 를 설치 한 셸 정렬 알고리즘
    구체 적 인 알고리즘 [참고서 목록 [12]]
알고리즘 분석
1. 증분 시퀀스 선택
    셸 정렬 의 실행 시간 은 증분 시퀀스 에 의존 합 니 다.
    좋 은 증분 시퀀스 의 공 통 된 특징:
① 마지막 증 가 는 1 이 어야 한다.
② 서열 중의 값 (특히 인접 한 값) 이 서로 배수 가 되 는 상황 을 피해 야 한다.
    어떤 사람 은 대량의 실험 을 통 해 현재 비교적 좋 은 결 과 를 제시 했다. n 이 비교적 클 때 비교 와 이동 횟수 는 약 nl. 25 에서 1.6n. 25 사이 이다.
2. Shell 정렬 의 시간 성능 은 정렬 을 직접 삽입 하 는 것 보다 좋 습 니 다.
    힐 정렬 의 시간 성능 이 정렬 을 직접 삽입 하 는 것 보다 좋 은 이유:
① 파일 의 초기 상태 가 기본적으로 질서 가 있 을 때 정렬 을 직접 삽입 하 는 데 필요 한 비교 와 이동 횟수 가 비교적 적다.
② n 값 이 시간 에 비해 n 과 n2 의 차이 도 비교적 적다. 즉, 정렬 을 직접 삽입 하 는 가장 좋 은 시간 복잡 도 O (n) 와 최 악의 시간 복잡 도 0 (n2) 의 차이 가 크 지 않다.
③ 힐 정렬 을 시작 할 때 증 가 량 이 많 고 그룹 이 많 으 며 각 그룹의 기록 수량 이 적 기 때문에 각 그룹 에 직접 삽입 하 는 것 이 빠 르 고 나중에 증 가 된 di 가 점점 줄 어 들 며 그룹 수 는 점점 줄 어 들 었 으 며 각 그룹의 기록 수량 은 점점 증가 했다. 그러나 di - 1 을 거리 로 배열 하여 파일 이 질서 있 는 상태 에 가 까 워 졌 기 때문에 새로운 정렬 과정 도 비교적 빠르다.
    따라서 힐 의 순 서 는 효율 적 으로 직접 삽입 하 는 것 보다 개선 되 었 다.
3. 안정성
    힐 의 순 서 는 불안정 하 다.상기 사례 를 참조 하여 이 예 에서 두 개의 같은 키워드 49 는 정렬 전후의 상대 적 인 순서 에 변화 가 생 겼 다.
알고리즘 프로그램

void shellsort(int n,int a[])
//    
//           
//      n   d1       ，
//          d1  。
//     dl             。
//             ；  ，
//      d2<d1          ，
//       dt=1(dt<dt-l<…<d2<d1)，                     。
//                。
//     (n*logn)
{
int t=0,s=1,d,i,k,m,x,j;
while(s<n)
{
 t++;
 s=s*2;
}
d=(n+1)/2;
for(m=1;m<=t;m++)//  t   
{
 k=d;
 for(i=k;i<n;i++)//            
 {
  x=a[i];
  j=i-k;
  while((x<a[j])&&(j>=0))//              
  {
   a[j+k]=a[j];
   j=j-k;
  }
  a[j+k]=x; 
 }
 d=d/2;
}
}