《 C 알고리즘 》 독서 노트 8: shell sort

3221 단어
힐 정렬 셸 sort 는 변종 삽입 정렬 insertsort 입 니 다.일부 질서 있 는 데 이 터 를 직면 할 때 정렬 을 삽입 하 는 효율 은 O (n) 에 가깝다. 정렬 을 삽입 하 는 교환 효율 은 역순 수 쌍 의 수량 에 달 려 있 기 때문이다.정렬 을 삽입 하 는 단점 은 두 번 의 인접 한 외부 순환 이 너무 먼 항목 을 교환 할 수 없다 는 것 입 니 다. 왼쪽 에서 오른쪽으로 순서대로 진행 해 야 합 니 다. 운 이 좋 지 않 으 면 최소 키 가 있 는 항목 이 맨 오른쪽 에 있 으 면 N 단계 가 있어 야 끝 납 니 다.
void insert_sort2(int *a, int l, int r)
{
    int step = 0;
iter1:
    for(int i = l + 1; i <= r; ++ i)
    {
        int j = i;
        int v = a[i];
        while(j >= l + 1 && LT(v, a[j - 1]))
        {
            a[j] = a[j - 1];
            -- j;
            ++ step;
        }
        a[j] = v;
    }
    printf("insert sort step: %d
", step);
}

힐 정렬 의 개선 은 외부 순환 iter 1 밖에서 오프셋 h 를 추가 하 는 것 입 니 다. 매번 재 정렬 한 후에 다음 과 같은 성질 을 얻 을 수 있 습 니 다. h 마다 하 나 를 취하 여 이 새 배열 을 질서 있 게 합 니 다.순서대로 오프셋 을 줄 이 고 마지막 으로 오프셋 을 1 로 한다.앞에서 말 한 삽입 정렬 의 성질 때문에 매번 정렬 은 삽입 정렬 으로 완성 할 수 있다.중요 한 것 은 편 이 량 의 선택 방식 이다.무 작위 로 생 성 된 N = 10000 의 데 이 터 를 통계 한 결과 다음 과 같은 몇 가지 오프셋 이 비교적 좋 은 것 으로 나 타 났 다.(1):4095 2047 1023 511 255 127 63 31 15 7 3 1 hn=hn+1∗2+1 (2):3280 1093 364 121 40 13 4 1 hn=hn+1∗3+1
다음 방식 은 효과 가 좋 지 않다. (1): 4096 2048 1024 512 256 64 32 16 4 2 hn = hn + 1 * 8727
void shell_sort(int *a, int l, int r)
{
    int h;
    for(h = 1; h <= (r - l) / 4; h = 2 * h);
    int step = 0;
    for(; h; h /= 2)
    {
        printf("%d ", h);
        for(int i = l + h; i <= r; ++ i)
        {
            int j = i;
            int v = a[i];
            while(j >= l + h && LT(v, a[j - h]))
            {
                a[j] = a[j - h];
                j -= h;
                ++ step;
            }
            a[j] = v;
        }
    }
    printf("
shell sort step %d
", step);
}
[bash] read 명령
0 부터 1 까지 네트워크 보안 학습 [Linux 기초 편 - linux yum 명령]

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage