자바 로 힐 정렬 알고리즘 을 구현 하 는 간단 한 예제

간단 한 소개 힐 정렬 (증분 법 축소) 은 삽입 류 정렬 에 속 합 니 다. 셸 에서 제시 한 바 와 같이 힐 정렬 은 직접 삽입 정렬 에 대해 간단 한 개선 을 했 습 니 다. 이 는 정렬 에 삽 입 된 요소 간 의 간격 을 늘 리 고 간격 이 있 는 요소 에 정렬 을 삽입 하여 데이터 항목 을 큰 폭 으로 이동 시 켰 습 니 다. 이 데이터 항목 들 이 정렬 된 후에힐 정렬 알고리즘 은 데이터 항목 의 간격 을 줄 이 고 정렬 을 한 다음 에 순서대로 진행 합 니 다. 이 정렬 을 할 때 데이터 항목 간 의 간격 을 증분 이 라 고 하 는데 습관 적 으로 알파벳 h 로 이 증 가 를 표시 합 니 다.자주 사용 하 는 h 서열 은 Knuth 가 제기 한 것 으로 이 서열 은 1 부터 다음 과 같은 공식 을 통 해 생 긴 다.

h = 3 * h +1

거꾸로 프로그램 은 h 시퀀스 를 역방향 으로 계산 해 야 합 니 다. 사용 해 야 합 니 다.

h=(h-1)/3

코드 구현 코드 1:

public static void shellSort(int[] arr){
  int temp;
  for (int delta = arr.length/2; delta>=1; delta/=2){               //           
    for (int i=delta; i=delta && arr[j] 
 

구현 코드 2:

public static void shellSort2(int[] arr){
  int delta = 1;
  while (delta < arr.length/3){//generate delta
    delta=delta*3+1;  // : 1, 4, 13, 40, 121, ...
  }    
  int temp;
  for (; delta>=1; delta/=3){
    for (int i=delta; i=delta && arr[j] 
 

위의 프로그램 은 직접 삽입 법 과 비교 하면 직접 삽입 정렬 과 의 차이 점 을 발견 할 수 있 습 니 다. 정렬 에 있 는 h 를 직접 삽입 하면 1 로 대 체 됩 니 다.Shell 정렬 은 불안정 합 니 다. 공간 지출 도 O (1) 이 고 시간 지출 은 O (N3/2) ~ O (N7/6) 사이 로 추정 합 니 다.