[고전 알고리즘]: 힐 정렬 의 실현

힐 정렬 은 별 쓸모 가 없다 고 생각 합 니 다.
또한 이러한 정렬 은 정렬 을 삽입 하 는 실현 메커니즘 과 매우 비슷 합 니 다. 그룹 코드 를 조금 만 추가 한 다음 에 그룹 삽입 을 하면 됩 니 다. =
이전 글 의 삽입 순 서 를 참고 하 십시오:http://blog.csdn.net/qq_23100787/article/details/50054773
다음은 힐 의 정렬 원리 에 대한 소개 입 니 다.
힐 정렬 의 실질 은 그룹 을 나 누 어 정렬 을 삽입 하 는 것 이다. 이 방법 은 증분 정렬 을 축소 하 는 것 이 라 고도 부 르 는데 DL. 셸 이 1959 년 에 제기 한 것 으로 이름 을 얻 었 다.
 
이 방법의 기본 사상 은 먼저 전체 대기 요소 서열 을 몇 개의 키 서열 (특정한 '증분' 요소 로 구 성 된) 로 나 누 어 각각 정렬 을 한 다음 에 차례대로 증 가 를 줄 이 고 정렬 을 한 다음 에 전체 서열 중의 요소 가 기본적으로 질서 가 있 을 때 (증 가 량 이 충분 하 다) 전체 요 소 를 직접 삽입 하여 정렬 하 는 것 이다.정렬 을 직접 삽입 하 는 것 은 요소 가 기본적으로 질서 가 있 는 상황 에서 (가장 좋 은 상황 에 가깝다) 효율 이 높 기 때문에 힐 정렬 은 시간 효율 에 있어 서 앞의 두 가지 방법 보다 비교적 높 아 졌 다.
 
n = 10 의 한 배열 49, 38, 65, 97, 26, 13, 27, 49, 55, 4 를 예 로 들 면
첫 번 째 gap = 10 / 2 = 5
49   38   65   97   26   13   27   49   55   4
1A                                        1B
        2A                                         2B
                 3A                                         3B
                         4A                                          4B
                                  5A                                         5B
1A, 1B, 2A, 2B 등 은 그룹 별로 표시 되 고 숫자 는 같은 그룹 에 표시 되 며 대문자 로 는 이 그룹의 몇 번 째 요소 임 을 나타 내 며 매번 같은 그룹의 데 이 터 를 직접 삽입 하여 정렬 합 니 다.즉 5 조 (49, 13) (38, 27) (65, 49) 로 나 뉘 었 다.  (97, 55)  (26, 4) 이렇게 각 조 가 정렬 되면 (13, 49)  (27, 38)  (49, 65)  (55, 97)  (4, 26), 이하 동일.
두번째 gap = 5 / 2 = 2
정렬 후
13   27   49   55   4    49   38   65   97   26
1A             1B             1C              1D            1E
        2A               2B             2C             2D              2E
세 번 째 gap = 2 / 2 = 1
4   26   13   27   38    49   49   55   97   65
1A   1B     1C    1D    1E      1F     1G    1H     1I     1J
네 번 째 gap = 1 / 2 = 0 정렬 이 완료 되면 배열 을 얻 을 수 있 습 니 다:
4   13   26   27   38    49   49   55   65   97
그 다음 에 상기 원리 에 대한 소 개 를 통 해 우 리 는 추 가 된 그룹 gap 크기 가 사실은 정렬 을 삽입 하 는 부담 이라는 것 을 알 아야 한다. 그러면 코드 를 간단하게 쓸 수 있 고 코드 를 다음 과 같이 첨부 할 수 있다.

//     
#include <iostream>
using namespace std;
void insert(int a[],int n){
	for(int gap =n/2;gap>0;gap/=2){
		for(int i=gap;i<n;i++){
			for(int j=i-gap;j>=0 &&a[j]>a[j+gap];j-=gap){
				swap(a[j],a[j+gap]);
			}
		}
	}
}
void swap(int *a,int *b){
	int temp = *a;
	*a = *b;
	*b = temp;
}
int main(){
	int a[] = {2,7,8,9,3,6,5,1};
	insert(a,8);
	for(int i=0;i<8;i++){
		cout<<a[i]<<" ";
	}
}

자세히 살 펴 보면 이전 글 과 의 삽입 정렬 이 조금 차이 가 나 는 그룹 메커니즘 을 발견 할 수 있 습 니 다. =