힐 정렬 알고리즘 원리 및 JAVA 구현

힐 정렬 (증 량 정렬 축소) 기본 사상: 알고리즘 은 먼저 정렬 할 그룹의 수 를 특정한 증 량 d (n / 2, n 은 정렬 할 수의 개수) 에 따라 몇 개의 그룹 으로 나 누고 각 그룹 에 기 록 된 아래 표 의 차 이 는 d 이다.각 그룹의 모든 요 소 를 정렬 에 직접 삽입 한 다음 에 작은 증분 (d / 2) 으로 그룹 을 나 누고 각 그룹 에 직접 정렬 을 삽입 합 니 다.증분 이 1 로 줄 었 을 때 정렬 을 직접 삽입 한 후 정렬 이 완료 되 었 습 니 다.복잡 도: 평균 시간 복잡 도 O (n 1.25)  공간 복잡 도 O (1) 실례 도 증분 시퀀스 선택    셸 정렬 의 실행 시간 은 증분 시퀀스 에 의존 합 니 다.    좋 은 증 량 서열 의 공 통 된 특징: ① 마지막 증 가 는 반드시 1 이 어야 한다.② 서열 중의 값 (특히 인접 한 값) 이 서로 배수 가 되 는 상황 을 피해 야 한다.    어떤 사람 은 대량의 실험 을 통 해 현재 비교적 좋 은 결 과 를 제시 했다. n 이 비교적 클 때 비교 와 이동 횟수 는 약 nl. 25 에서 1.6n. 25 사이 이다.Shell 정렬 의 시간 성능 은 정렬 을 직접 삽입 하 는 것 보다 좋 습 니 다.    힐 정렬 의 시간 성능 이 정렬 을 직접 삽입 하 는 것 보다 좋 은 이 유 는 ① 파일 의 초기 상태 가 기본적으로 질서 가 있 을 때 정렬 을 직접 삽입 하 는 데 필요 한 비교 와 이동 횟수 가 비교적 적다.② n 값 이 시간 에 비해 n 과 n2 의 차이 도 비교적 적다. 즉, 정렬 을 직접 삽입 하 는 가장 좋 은 시간 복잡 도 O (n) 와 최 악의 시간 복잡 도 0 (n2) 의 차이 가 크 지 않다.③ 힐 정렬 을 시작 할 때 증 가 량 이 많 고 그룹 이 많 으 며 각 그룹의 기록 수량 이 적 기 때문에 각 그룹 에 직접 삽입 하 는 것 이 빠 르 고 나중에 증 가 된 di 가 점점 줄 어 들 며 그룹 수 는 점점 줄 어 들 었 으 며 각 그룹의 기록 수량 은 점점 증가 했다. 그러나 di - 1 을 거리 로 배열 하여 파일 이 질서 있 는 상태 에 가 까 워 졌 기 때문에 새로운 정렬 과정 도 비교적 빠르다.    따라서 힐 의 순 서 는 효율 적 으로 직접 삽입 하 는 것 보다 개선 되 었 다.안정성: 힐 의 순 서 는 불안정 하 다.JAVA 소스 코드 (성공 실행):

	public static void shellSort(int []array){
		double increment = array.length;//    
		int dk,sentinel,k;
		while (true) {
			increment = (int)Math.ceil(increment/2);//        
			dk = (int)increment;//      
			for (int i = 0; i < dk; i++) {
				//        ，          。       1，            
				for (int j = i+dk; j < array.length; j+=dk) {
					k = j - dk;
					sentinel = array[j];//   
					while (k >= 0 && sentinel < array[k]) {
						array[k+dk] = array[k];//k+dk       
						k = k - dk;
					}
					array[k+dk] = sentinel;
				}
			}
			// dk 1   ，          
			if (dk == 1) {
				break;
			}
		}
	}