Une brève analyse de l'algorithme de tri Java Hill (Shell)

Prenez d'abord un entier d1 inférieur à n comme premier incrément et divisez tous les enregistrements du fichier en groupes d1. Tous les enregistrements dont la distance est un multiple de dl sont placés dans le même groupe. Effectuez d'abord un tri par insertion directe dans chaque groupe ; puis prenez le deuxième incrément d2Cette méthode est essentiellement une méthode d'insertion groupée.

Diagramme schématique :

Code source

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);
    }
}

Résultats d'exécution :

Le tri des shells est instable, sa surcharge spatiale est également O(1) et la surcharge temporelle est estimée entre O(N3/2)~O(N7/6)

Plus d'analyse de Java Pour les articles liés à l'algorithme de tri Hill (Shell), veuillez faire attention au site Web PHP chinois !