10 대 정렬 알고리즘 - 힐 정렬 (요소 교환 법 과 배열 요소 이동 법 C 언어)

힐 정렬 (원소 교환 법 과 수조 원소 이동 법)
힐 정렬 (Shell 's Sort) 은 정렬 을 삽입 하 는 일명' 증 량 축소 정렬 '(Diminishing Increment Sort) 으로 정렬 알고리즘 을 직접 삽입 하 는 효율 적 인 개선 버 전 입 니 다.힐 정렬 은 불안정 정렬 알고리즘 입 니 다.이 방법 은 D. L. Shell 이 1959 년 에 제기 한 것 으로 이름 을 얻 었 다.
기본 사상
먼저 첫 번 째 정렬 은 하나의 정렬 대기 서열 을 증 량 (증 량 은 두 원소 위치의 간격) 에 따라 몇 개의 그룹 으로 나 눈 다음 에 각 그룹 에 정렬 을 삽입 하고 첫 번 째 정렬 이 끝 난 후에 한다.증 가 량 을 줄 이 고 여러 그룹 으로 나 누 어 삽입 정렬 을 합 니 다. 증 가 량 이 1 일 때 까지 모든 데 이 터 를 같은 그룹 에 놓 고 정렬 을 직접 삽입 할 때 까지 질서 있 는 순 서 를 얻 을 수 있 습 니 다.증 가 량 을 선택 하 는 것 은 일반적으로 첫 번 째 추출 서열 의 절반 은 증 가 량 이 고, 이후 에는 매번 반 으로 줄 여 증 가 량 이 1 이 될 때 까지 한다.
도해 설명 은 아래 링크 로 가서 보 는 것 을 권장 합 니 다.
나의 참고 문헌: 힐 정렬 - 간단 하고 알 기 쉬 운 도해 설명 아래 이 링크 는 증 가 된 다른 최적화 방법 힐 정렬 원리 에 대한 분석
원소 교환 법 과 수조 원소 이동 법 으로 힐 정렬 을 실현 하 다

#include 
#include 

//      
void swap(int *a,int *b)
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}
//    ，                 
void Hill_Sort1(int a[],int n)
{   //  increment，       
    for (int increment = n/2 ; increment > 0; increment/=2)
    {
        //  increment   ，                 
        for (int i = increment; i < n; i++)
        {
            int j = i;
            while (j-increment >=0 && a[j]<a[j-increment])
            {
                swap(&a[j],&a[j-increment]);
                j-=increment;
            }
            
        }
        
    }
    
}
//    ，                   
void Hill_Sort2(int a[],int n)
{
    //  increment，       
    for (int increment = n/2; increment < 0; increment/-2)
    {
        //  increment   ，                 
        for (int i = increment; i < n; i++)
        {
            int j = i;
            int temp = a[j];
            if (a[j]<a[j-increment])
            {
                while (j-increment >= 0 && temp < a[j-increment])
                {
                    //   
                    a[j]=a[j-increment];
                }
                a[j] = temp;
            }
            
        }
        
    }
    
}
void main()
{
    int a[]={12,13,46,56,16,49,79,45,15,59,20};
    int n=sizeof(a)/sizeof(int);    //      
    int i;
    Hill_Sort1(a,n);  //     
    Hill_Sort2(a,n);  //       
    for ( i = 0; i < n; i++)
    {
        printf("%d ",a[i]);
    }
    system("pause");   //       

}