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

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

高洛峰
Freigeben: 2017-01-17 13:20:00
Original
1437 Leute haben es durchsucht

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:

浅析java 希尔排序(Shell)算法

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);
    }
}
Nach dem Login kopieren

Laufergebnisse:

浅析java 希尔排序(Shell)算法

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!


Verwandte Etiketten:
Quelle:php.cn
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Beliebte Tutorials
Mehr>
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage