삼 백화 고전 알고리즘 시리즈 셸 정렬 실현

산 은 가방 에 삽 입 된 정수 정렬 정렬 이다.이 방법 은 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
 
다음은 정 의 를 엄 격 히 따 른 힐 정렬 을 드 리 겠 습 니 다.

void shellsort1(int a[], int n)

{

	int i, j, gap;



	for (gap = n / 2; gap > 0; gap /= 2) //  

		for (i = 0; i < gap; i++)        //      

		{

			for (j = i + gap; j < n; j += gap) 

				if (a[j] < a[j - gap])

				{

					int temp = a[j];

					int k = j - gap;

					while (k >= 0 && a[k] > temp)

					{

						a[k + gap] = a[k];

						k -= gap;

					}

					a[k + gap] = temp;

				}

		}

}

매우 뚜렷 하 다.위의 셸 sort 1 코드 는 힐 의 순 서 를 직관 적 으로 이해 하 는 데 도움 이 되 지만 코드 의 양 이 너무 많다.깔끔 하지 못 하고 또렷 하지 못 하 다.따라서 개선 과 최 적 화 를 실시 하고 두 번 째 순 서 를 예 로 들 면 매번 1A 에서 1E, 2A 에서 2E 까지 이다.1B 부터먼저 1A 와 비교 한 다음 에 2B 와 2A 를 비교 한 다음 에 1C 와 앞의 자기 그룹 내의 데 이 터 를 비교 합 니 다.이러한 매번 배열 의 두 번 째 gap 요소 부터 시작 합 니 다.모든 요소 와 자신의 그룹 내의 데 이 터 를 직접 삽입 하여 정렬 하 는 것 도 분명 정확 하 다.

void shellsort2(int a[], int n)

{

	int j, gap;

	

	for (gap = n / 2; gap > 0; gap /= 2)

		for (j = gap; j < n; j++)//    gap     

			if (a[j] < a[j - gap])//                     

			{

				int temp = a[j];

				int k = j - gap;

				while (k >= 0 && a[k] > temp)

				{

					a[k + gap] = a[k];

					k -= gap;

				}

				a[k + gap] = temp;

			}

}

정렬 부분 에 직접 삽입 하기 백화 고전 알고리즘 시리즈 의 두 번 째 직접 삽입 정렬 의 세 가지 실현  정렬 을 직접 삽입 하 는 세 번 째 방법 은 다음 과 같 습 니 다.

void shellsort3(int a[], int n)

{

	int i, j, gap;



	for (gap = n / 2; gap > 0; gap /= 2)

		for (i = gap; i < n; i++)

			for (j = i - gap; j >= 0 && a[j] > a[j + gap]; j -= gap)

				Swap(a[j], a[j + gap]);

}

이렇게 하면 코드 가 매우 간결 하 게 변 한다.
  
부주: 위의 힐 정렬 의 보폭 선택 은 n/2 부터 시작 하여 매번 반 으로 줄 이 고 끝 날 때 까지 1.사실 그것 은 독자 의 흥 미 를 가정 하여 이해 하 는 또 다른 효과 적 인 절차 선택 이 있 을 수 있다.케이스 정렬 절차 에 대한 설명 을 보 았 습 니 다. 위 키 피 디 아:
http://zh.wikipedia.org/wiki/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F