삽입 정렬: 힐 정렬 (Shell 's Sort)

힐 의 순 서 는 1959 년 에 D. L. Shell 에서 제 기 된 것 으로 직접적인 순 서 는 비교적 개선 되 었 다.힐 정렬 은 축소 증분 정렬 이 라 고도 한다.
기본 사상:
먼저 전체 정렬 을 기다 리 는 기록 서열 을 여러 개의 하위 서열 로 나 누 어 각각 정렬 을 직접 삽입 하고 전체 서열 의 기록 이 '기본 질서' 가 있 을 때 전체 기록 을 순서대로 정렬 을 삽입 합 니 다.상대 적 으로 직접 정렬 이 비교적 개선 되 었 다.
조작 방법:
1. 증분 시퀀스 t1, t2,..., tk 를 선택 하 십시오. 그 중에서 ti > tj, tk = 1;
2. 증 량 서열 개수 k 에 따라 서열 을 k 차례 정렬 한다.
3. 매 차례 의 정렬 은 대응 하 는 증 량 ti 에 따라 대기 서열 을 약간의 길이 가 m 인 하위 서열 로 나 누 어 각 하위 표 에 직접 삽입 하여 정렬 한다.증분 인자 가 1 일 때 전체 서열 은 하나의 표 로 처리 되 고 표 의 길 이 는 전체 서열 의 길이 이다.
알고리즘 구현:
우 리 는 증분 서열 d = {n/2, n/4, n/8...................................................................그룹 을 나 누고 각 그룹 에 정렬 을 직접 삽입 합 니 다.1 까지 증 가 를 계속 줄 이 고 마지막 으로 정렬 을 직접 삽입 하여 정렬 을 완성 합 니 다.

//       
void print(int array[], int length, int i) {
    printf("i=%d:",i);
    for (int j = 0; j < length; j++) {
        printf(" %d ", array[j]);
    }
    printf("
");
}

//            ，   int dk      ，         ，dk=1
void ShellInsertSort(int array[], int length, int dk) {
    for (int i = dk; i < length; i++) {
        if (array[i] < array[i-dk]) { //   i     i-dk  ，    ；    ，        
            int j = i - dk;
            int sentry = array[i]; //      ，        
            array[i] = array[i-dk]; //         
            while (j >= 0 && sentry < array[j]) { //            
                array[j+dk] = array[j];
                j -= dk; //     
            }
            array[j+dk] = sentry; //        
        }
        print(array, length, i); //          
    }
}

//     d（n/2，n        ）      
void ShellSort(int array[], int length) {
    int dk = length / 2;
    while (dk >= 1) {
        ShellInsertSort(array, length, dk);
        dk = dk / 2;
    }
}

int main(int argc, const char * argv[]) {
    int arrayShellSort[8] = { 49, 38, 65, 97, 76, 13, 27, 49 };
    //ShellInsertSort(arrayShellSort, 8, 1); //       
    ShellSort(arrayShellSort, 8); //       
    printf("
");
    
    return 0;
}

총결산
힐 정렬 시효 분석 은 매우 어렵다. 관건 코드 의 비교 횟수 와 기록 이동 횟수 는 증 량 인자 서열 d 의 선택 에 의존 하고 특정한 상황 에서 관건 코드 의 비교 횟수 와 기록 의 이동 횟수 를 정확하게 추산 할 수 있다.현재 로 서 는 가장 좋 은 증 량 인자 서열 을 선택 하 는 방법 을 제시 하 는 사람 이 없다.증 량 인자 서열 은 각종 취 법 이 있 을 수 있 고 기 수 를 취 하 는 것 도 있 으 며 질 수 를 취 하 는 것 도 있 지만 주의해 야 한다. 증 량 인자 중 1 을 제외 하고 공인 자가 없고 마지막 증 량 인 자 는 반드시 1 이 어야 한다.힐 정렬 방법 은 불안정한 정렬 방법 이다.