Eine kurze Analyse des Java-Hill-Sortieralgorithmus (Shell).

Nehmen Sie zunächst eine Ganzzahl d1 kleiner als n als erstes Inkrement und teilen Sie alle Datensätze in der Datei in d1-Gruppen auf. Alle Datensätze, deren Abstand ein Vielfaches von dl ist, werden in derselben Gruppe platziert. Führen Sie zuerst eine direkte Einfügungssortierung innerhalb jeder Gruppe durch. Nehmen Sie dann das zweite Inkrement d2Diese Methode ist im Wesentlichen eine gruppierte Einfügemethode.

Schematische Darstellung:

Quellcode

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

Laufergebnisse:

Shell-Sortierung ist instabil, ihr Speicherplatzaufwand beträgt ebenfalls O(1) und der Zeitaufwand wird auf O(N3/2)~O(N7/6) geschätzt

Weitere Analyse von Java Für Artikel zum Hill-Sortierungsalgorithmus (Shell) beachten Sie bitte die chinesische PHP-Website!