Hier ist zunächst mein Shell-Sortiercode (unter Verwendung von Java):

public char[] shellSort(char[] chars) {
    int n = chars.length;
    int increment = n / 2;
    while(increment > 0) {
        int last = increment;
        while(last < n) {
            int current = last - increment;
            while(current >= 0) {
                if(chars[current] > chars[current + increment]) {
                    //swap
                    char tmp = chars[current];
                    chars[current] = chars[current + increment];
                    chars[current + increment] = tmp;
                    current -= increment;
                }
                else { break; }
            }
            last++;
        }
        increment /= 2;
    }
    return chars;
}

Handelt es sich hierbei um eine korrekte Implementierung der Shell-Sortierung (wobei vorerst die effizienteste Lückensequenz vergessen wird, z. B. 1,3,7,21 ...)? Ich frage, weil ich gehört habe, dass die bestmögliche Zeitkomplexität für Shell Sort O (n) ist. (Sehenhttp://en.wikipedia.org/wiki/Sorting_algorithm). Ich kann nicht sehen, dass dieser Grad an Effizienz durch meinen Code erreicht wird. Wenn ich Heuristiken hinzufüge, dann ja, aber wie es aussieht, nein.

Abgesehen davon, meine Hauptfrage jetzt - ich habe Schwierigkeiten, die Big O-Zeit-Komplexität für meine Shell-Sortierimplementierung zu berechnen. Ich habe festgestellt, dass die äußerste Schleife als O (log n), die mittlere Schleife als O (n) und die innerste Schleife auch als O (n), aber mir ist klar, dass die beiden inneren Schleifen eigentlich nicht O ( n) - sie wären viel weniger als das - was sollten sie sein? Weil dieser Algorithmus offensichtlich viel effizienter läuft als O ((log n) n ^ 2).

Jede Anleitung wird sehr geschätzt, da ich sehr verloren bin! : P