자바 상세 힐(Shell)정렬

최근 일자 리 를 찾 아 필기시험 문 제 를 풀 고 정렬 알고리즘 을 시험 해 보 았 습 니 다.힐 의 정렬 을 다시 한 번 복습 해 보 았 을 때 이해 하지 못 했 습 니 다!!⊙⊙⊙b 땀 이 나 기 때문에 첫 번 째 코드 를 볼 때 겪 는 문 제 를 정리 하여 다시 잊 지 않도록 하 세 요.다 시 는 잊 지 마 세 요!!
 
     힐 정렬(축소 증분 법)은 삽입 류 정렬 에 속 하 며 전체 무 서열 을 몇 개의 작은 하위 서열 로 나 누 어 각각 삽입 정렬 을 하 는 것 이다.힐 정렬 이 불안정 합 니 다.O(1)의 추가 공간,시간 복잡 도 는 O(N*(logN)^2)입 니 다.최 악의 경우 집행 효율 은 평균 상황 에서 의 집행 효율 에 비해 크게 다 르 지 않다.
    힐 정렬 간격 시퀀스 함수 h=h*3+1
    힐 의 정렬 이 삽입 정렬 보다 빠 른 이 유 는 h 값 이 많 을 때 데이터 항목 의 정렬 마다 이동 하 는 요소 의 개수 가 적 지만 이동 하 는 거리 가 길 기 때문에 매우 효율 적 입 니 다.h 값 이 줄 어 들 면 정렬 마다 이동 하 는 요소 의 개수 가 증가 하지만 이때 의 데이터 항목 은 최종 정렬 후의 위치 에 가 깝 고 정렬 을 삽입 하면 더욱 효과 적 입 니 다.
직접 코드 첨부
 

public class ShellSort {

	static void sort(int[] array) {

		int out, in, tmp;

		int len = array.length;

		int h = 1; 

		while(h < len / 3) //     h   

			h = h * 3 + 1;

		

		while(h > 0){ //           h         

			/*

			 * out    h  ？                   ，0, h, 2h, 3h, ...

			 *      while    1   ，          ，     ，             ，            ，      h     

			 * out       out < len？

			 *       ，        

			 * 

			 *           

			 *      10       ，     0 ~ 9   

			 *  h = 4           ，     

			 * （0 4 8）（1 5 9）（2 6）（3 7）

			 *           ，             （         ，        ），                 。

			 *          ，  for                      ，   3 ，   4  ...           

			 *             

			 *  out = 4        （[0 4] 8）

			 *  out = 5 （[1 5] 9）

			 *  out = 6 （[2 6]）

			 *  out = 7 （[3 7]）

			 *  out = 8 （[0 4 8]）

			 *  out = 9 （[1 5 9]）

			 * h = 4    ，  h = (h - 1) / 3 = 1    for  

			 * h = 1      h = 4   ，               ，            ，        ，            

			 * 

			 */

			for(out = h; out < len; out++){ //     out               

				//                    

				tmp = array[out];

				in = out;

				/*

				 *       while     ，   while   h  ，      h  ，   in -= h  

				 * while(in > 0 && array[in - 1] > tmp){

				 * array[in] = array[in - 1];

				 * in--;

			     * }

			     * array[in] = tmp;

				 * 

				 */

				while(in > h -1 && array[in - h] >= tmp){

					array[in] = array[in - h];

					in -= h;

				}

				array[in] = tmp;

//				for(int i = 0; i < len; i++)

//					System.out.print(array[i] + " ");

//				System.out.println();

								

			}

			

			//     

			h = (h - 1) / 3;

		}

	}

}