정렬 알고리즘 (6) - 힐 정렬 (셸 정렬)

2155 단어 정렬 알고리즘
학습 정렬 사이트:https://www.toptal.com/developers/sorting-algorithms 본 논문 의 정렬 방식 은 어 릴 때 부터 큰 순서 까지 를 기준 으로 한다.
의 원리
- 정렬 을 직접 삽입 하 는 최적화 알고리즘 – 배열 을 아래 표 시 된 일정한 증분 에 따라 그룹 을 나 누고 각 그룹 에 직접 정렬 을 삽입 합 니 다.증 량 이 점점 줄 어 들 면서 그룹의 요소 가 점점 많아 지고 증 량 이 1 일 때 까지 그룹 에 모든 요 소 를 포함 하고 정렬 이 완료 되면 알고리즘 이 결 제 됩 니 다.
주의 점
4. 567917. 최소 증 가 는 1 이 어야 합 니 다
4. 567917. 힐 의 정렬 이 각 조 에서 실 행 된 후에 정렬 이 완성 에 한 걸음 가 까 워 졌 기 때문이다.또 직접 삽입 정렬 이 정렬 에 가 까 울 수록 효율 이 높 기 때문이다.그래서 힐 의 정렬 은 직접 삽입 하 는 것 보다 우수 하 다 (비교 와 교환 횟수 가 적다)
예시
    @Override
    int[] sort(int[] data) {
        int len = data.length;
        // Hibbard      
        int hibbard = 1;
        while(hibbard < len/2) {
            hibbard = hibbard*2+1;
        }
        //       ,              
        for (int i = hibbard; i > 0; i=(i-1)/2) {
            //     ,      j  ,  i      
            for (int j = i; j < len; j+=i) {
                int temp = data[j];//       
                int k = j - i;
                while(k >= 0 && data[k] > temp) {
                    data[k+i] = data[k];
                    k-=i;
                }
                data[k+i] = temp;
            }
        }
        return data;
    }

좋은 웹페이지 즐겨찾기