Le temps de la complexité de tri de Shell?

Tout d'abord, voici mon tri de Shell code (en 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;
}

Est-ce une mise en œuvre correcte de tri de Shell (en oubliant pour l'instant sur le plus efficace de l'écart de la séquence par exemple, 1,3,7,21...)? Je demande parce que j'ai entendu dire que le meilleur des cas, le temps de la complexité de Tri de Shell est O(n). (Voir http://en.wikipedia.org/wiki/Sorting_algorithm). Je ne vois pas ce niveau d'efficacité réalisés par mon code. Si j'ai ajouté de l'heuristique, alors ouais, mais comme il est, pas.

Cela étant dit, ma question principale, maintenant je vais avoir de la difficulté à calculer le Big O moment de la complexité pour mon tri de Shell de mise en œuvre. J'ai identifié que les extérieurs de la boucle que O(log n), le milieu de la boucle que O(n), et le plus intérieur de la boucle aussi que O(n), mais je me rends compte à l'intérieur de deux boucles, ne serait O(n) - ils seraient beaucoup moins que ce que devraient-ils être? Car il est évident que cet algorithme fonctionne beaucoup plus efficacement que O((log n) n^2).

De toute orientation est apprécié, comme je suis très perdu! 😛

OriginalL'auteur Matt Larsen | 2012-10-07