먼저 첫 번째 증분으로 N보다 작은 정수 D1을 가져 와서 파일의 모든 레코드를 D1 그룹으로 나눕니다. 거리 DL의 배수가있는 모든 레코드는 동일한 그룹에 배치됩니다. 먼저 각 그룹에 정렬을 삽입 한 다음 두 번째 증분 D2 <D1을 취하고 증가 된 DT = 1 (dt <dt-l <;… <d2 <d1)까지 반복하십시오. 모든 레코드는 동일한 그룹에 배치되어 직접 정렬됩니다.
이 방법은 본질적으로 그룹화 삽입 방법입니다.
개략도:
소스 코드
코드 사본은 다음과 같습니다.
패키지 com.zc.manythread;
/**
*
* @author 나는
*
*/
공개 클래스 쉘 소트 {
공개 정적 int count = 0;
public static void shellsort (int [] data) {
// 최대 H 값을 계산합니다
int h = 1;
while (h <= data.length / 3) {
H = H * 3 + 1;
}
while (h> 0) {
for (int i = h; i <data.length; i += h) {
if (data [i] <data [i -h]) {
int tmp = data [i];
int j = i -h;
while (j> = 0 && data [j]> tmp) {
데이터 [j + h] = 데이터 [j];
j- = h;
}
데이터 [J + H] = TMP;
인쇄 (데이터);
}
}
// 다음 H 값을 계산합니다
H = (H -1) / 3;
}
}
public static void print (int [] data) {
for (int i = 0; i <data.length; i ++) {
System.out.print (데이터 [i] + "/t");
}
System.out.println ();
}
public static void main (String [] args) {
int [] data = new int [] {4, 3, 6, 2, 1, 9, 5, 8, 7};
인쇄 (데이터);
쉘 소트 (데이터);
인쇄 (데이터);
}
}
실행 결과 :
쉘 분류는 불안정하고 공간 오버 헤드는 O (1)이며 오버 헤드는 O (N3/2)와 O (N7/6) 사이에있는 것으로 추정됩니다.