Java Hill 정렬(쉘) 알고리즘에 대한 간략한 분석

먼저 n보다 작은 정수 d1을 첫 번째 증분으로 취하고 파일의 모든 레코드를 d1 그룹으로 나눕니다. 거리가 dl의 배수인 모든 레코드는 동일한 그룹에 배치됩니다. 먼저 각 그룹 내에서 직접 삽입 정렬을 수행한 다음 두 번째 증분 d2이 방법은 본질적으로 그룹화된 삽입 방법입니다.

개략도:

소스 코드

package com.zc.manythread;
/**
 * 
 * @author 偶my耶
 *
 */
public class ShellSort {
    public static int count = 0;
    public static void shellSort(int[] data) {
        // 计算出最大的h值
        int h = 1;
        while (h <= data.length / 3) {
            h = h * 3 + 1;
        }
        while (h > 0) {
            for (int i = h; i < data.length; i += h) {
                if (data[i] < data[i - h]) {
                    int tmp = data[i];
                    int j = i - h;
                    while (j >= 0 && data[j] > tmp) {
                        data[j + h] = data[j];
                        j -= h;
                    }
                    data[j + h] = tmp;
                    print(data);
                }
            }
            // 计算出下一个h值
            h = (h - 1) / 3;
        }
    }
    public static void print(int[] data) {
        for (int i = 0; i < data.length; i++) {
            System.out.print(data[i] + "\t");
        }
        System.out.println();
    }
    public static void main(String[] args) {
        int[] data = new int[] { 4, 3, 6, 2, 1, 9, 5, 8, 7 };
        print(data);
        shellSort(data);
        print(data);
    }
}

실행 결과:

쉘 정렬이 불안정하고 공간 오버헤드도 O(1)이며 시간 오버헤드는 O(N3/2)~O(N7/6) 사이로 추정됩니다.

java Hill For 추가 분석 정렬(쉘) 알고리즘과 관련된 기사는 PHP 중국어 웹사이트를 주목하세요!