希尔排序的时间复杂度是多少？

Question

首先，这是我的希尔排序代码（使用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;
}

这是一个正确的希尔排序实现吗（暂时忘记最有效的间隔序列，例如1,3,7,21...）？我问这个问题是因为我听说希尔排序的最佳情况时间复杂度为O(n)。（参见http://en.wikipedia.org/wiki/Sorting_algorithm）。但我认为我的代码无法实现这种效率水平。如果我向其中添加启发式算法，那么可以，但现在不行。

话虽如此，我的主要问题是 - 我很难计算出我的希尔排序实现的大O时间复杂度。我确定最外层循环为O(log n)，中间循环为O(n)，内部循环也为O(n)，但我意识到内部两个循环实际上不会是O(n) - 它们会远远小于这个值 - 应该是什么呢？因为显然，这种算法的运行效率比O((log n) n^2)要高得多。

非常感谢任何指导，因为我很迷茫！:P

- Matt Larsen

---

请查看shell-sort-java-example。 - nawfal

Answer 1

你的实现的最坏情况是Θ(n^2)，最好情况是O(nlogn)，这对于希尔排序来说是合理的。 最佳情况∊ O(nlogn): 当数组已经排序时，就会出现最佳情况。这意味着内部if语句永远不会为真，使得内部while循环成为一个恒定时间操作。使用你用于其他循环的界限可得到O(nlogn)。通过使用恒定数量的增量可以达到O(n)的最优情况。 最坏情况∊ O(n^2): 根据每个循环的上限，可以获得O((log n)n^2)的最坏情况。但是添加另一个变量作为间隔大小g。内部while中所需的比较/交换次数现在小于等于n/g。中间while所需的比较/交换次数小于等于n^2/g。将每个gap的比较/交换次数的上限相加：n^2 + n^2/2 + n^2/4 + ... <= 2n^2 ∊ O(n^2)。这与你使用的间隔的已知最坏情况复杂度相匹配。 最坏情况∊ Ω(n^2): 考虑一个数组，其中所有偶数位置的元素都大于中位数。在达到1的最后一个增量之前，奇数和偶数元素不会进行比较。最后一次迭代所需的比较/交换次数为Ω(n^2)。

- fgb

---

希尔排序使用的最坏比较次数并不总是二次的。使用3x+1增量，它是O(N^3/2)，而使用Sedgewick序列，则为O(N^4/3)。然而，对于上面代码中使用的序列，它绝对是二次的。请参见http://en.wikipedia.org/wiki/Shellsort#Gap_sequences。 - Nikunj Banka

我的讲义材料指出，目前已知的最佳运行时间是O(n^1.5)。之所以说“已知”，是因为至今仍未完成分析。 - Gewure

Answer 2

插入排序

如果我们分析一下

Original Answer:

static void sort(int[] ary) {
    int i, j, insertVal;
    int aryLen = ary.length;
    for (i = 1; i < aryLen; i++) {
        insertVal = ary[i];
        j = i;
        /*
         * while loop exits as soon as it finds left hand side element less than insertVal
         */
        while (j >= 1 && ary[j - 1] > insertVal) { 
            ary[j] = ary[j - 1];
            j--;
        }
        ary[j] = insertVal;
    }
}

因此，在平均情况下，while循环将在中途退出。

即1/2 + 2/2 + 3/2 + 4/2 + .... + (n-1)/2 = Theta((n^2)/2) = Theta(n^2)

你可以看到，即使除以2，我们也实现了(n^2)/2。

希尔排序只是使用间隔（如n/2、n/4、n/8、....、2、1）的插入排序，它利用了插入排序的最佳情况复杂度（即while循环退出），一旦我们找到插入元素左边的小元素，就会非常快地开始发生，因此它增加了总执行时间。

n/2 + n/4 + n/8 + n/16 + .... + n/n = n(1/2 + 1/4 + 1/8 + 1/16 + ... + 1/n) = nlogn（调和级数）

因此，它的时间复杂度接近于n(logn)^2。

"Original Answer"翻译成"最初的回答"

- Ziaullhaq Savanur