정렬정렬 의 힐 정렬 삽입 (증분 정렬 축소)

개술
힐 (Shell) 정렬 은 축소 증분 정렬 이 라 고도 부 르 며 삽입 정렬 입 니 다.그것 은 정렬 알고리즘 을 직접 삽입 하 는 위력 강화 판 이다.
코드 구현

/**
 * 基本思想：
 * 先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。
 * 所有距离为d1的倍数的记录放在同一个组中。
 * 先在各组内进行直接插入排序；然后，取第二个增量d2= 0 && temp < array[j]; j = j - gap) {
                    array[j + gap] = array[j];
                }

                array[j + gap] = temp;

            }
            System.out.format("gap = %d:\t", gap);
            printAll(array);
            gap = gap / 2; // 减小增量
        }

    }

    public static void main(String[] args) {
        int[] array = { 9, 1, 2, 5, 7, 4, 8, 6, 3, 5 };

        // 调用希尔排序方法
        希尔排序 shell = new 希尔排序();
        System.out.print("排序前:\t\t");
        shell.printAll(array);
        shell.shellSort(array);
        System.out.print("排序后:\t\t");
        shell.printAll(array);
    }

    // 打印完整序列
    public void printAll(int[] list) {
        for (int value : list) {
            System.out.print(value + "\t");
        }
        System.out.println();
    }

}

알고리즘 분석
이 예 를 들 어 힐 정렬 의 보폭 선택 은 n/2 에서 시작 하여 매번 반 으로 줄 이 고 마지막 까지 1 이다.이것 은 결코 가장 효율 적 인 보폭 선택 이 아니다.
힐 정렬 은 불안정 합 니 다. 우 리 는 한 번 의 삽입 정렬 이 안정 적 이라는 것 을 알 고 있 습 니 다. 그러나 서로 다른 삽입 정렬 과정 에서 같은 요 소 는 각자 의 삽입 정렬 에서 이동 할 수 있 고 마지막 에 안정성 이 어 지 러 워 집 니 다. 즉, 힐 정렬 에서 같은 데 이 터 를 교환 할 수 있 습 니 다.
힐 정렬 의 평균 시간 복잡 도 는 O (nlog2n) 이다.
정렬 과 힐 정렬 을 직접 삽입 하 는 비교
정렬 을 직접 삽입 하 는 것 이 안정 적 입 니 다.힐 의 순 서 는 불안정 하 다.정렬 을 직접 삽입 하 는 것 은 원본 기록 의 기본 적 이 고 질서 있 는 집합 에 더욱 적합 하 다.힐 정렬 의 비교 횟수 와 이동 횟수 는 직접 삽입 정렬 보다 적 고 N 이 클 수록 효과 가 뚜렷 하 다.힐 정렬 에서 증분 시퀀스 gap 의 취 법 은 만족 해 야 합 니 다. 마지막 걸음 길 이 는 1 이 어야 합 니 다.직접 정렬 을 삽입 하 는 것 도 체인 식 저장 구조 에 적용 된다.힐 정렬 은 체인 구조 에 적용 되 지 않 습 니 다.