算法 – Shell排序的时间复杂度？

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

这是Shell排序的正确实现(暂时忘记最有效的间隙序列 – 例如,1,3,7,21 …)？我问,因为我听说Shell Sort的最佳时间复杂度是O(n). (见http://en.wikipedia.org/wiki/Sorting_algorithm).我无法通过我的代码看到这种效率水平.如果我添加了启发式方法,那么是的,但是就目前而言,没有.

话虽如此,我现在的主要问题是 – 我很难计算Shell排序实现的Big O时间复杂度.我发现最外层循环为O(log n),中间循环为O(n),最内层循环也为O(n),但我发现内部两个循环实际上不是O( n) – 它们会比这要少得多 – 它们应该是什么？因为这个算法显然比O((log n)n ^ 2)运行得更有效.

任何指导都非常感谢,因为我很丢失！ ：P