7

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

这是 Shell 排序的正确实现吗（暂时忘记最有效的间隙序列 - 例如，1,3,7,21...）？我问是因为我听说 Shell 排序的最佳情况时间复杂度是 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

4

2 回答 2

10

您实现的最坏情况是 Θ(n^2)，最好情况是 O(nlogn)，这对于 shell 排序是合理的。

最好的情况∊ O(nlogn)：

最好的情况是数组已经排序。这意味着内部 if 语句永远不会为真，从而使内部 while 循环成为恒定时间操作。使用您用于其他循环的边界给出 O(nlogn)。通过使用恒定数量的增量可以达到 O(n) 的最佳情况。

最坏情况∊ O(n^2)：

给定每个循环的上限，在最坏的情况下，您会得到 O((log n)n^2)。但是为间隙大小 g 添加另一个变量。内部 while 所需的比较/交换次数现在 <= n/g。中间的比较/交换次数 <= n^2/g。将每个间隙的比较/交换次数的上限相加：n^2 + n^2/2 + n^2/4 + ... <= 2n^2 ∊ O(n^2)。这与您使用的间隙的已知最坏情况复杂性相匹配。

最坏情况∊Ω(n^2)：

考虑所有偶数定位元素都大于中位数的数组。奇数和偶数元素在我们达到最后一个增量 1 之前不会进行比较。最后一次迭代所需的比较/交换次数是 Ω(n^2)。

于 2012-10-07T18:36:17.457 回答
2

插入排序

在此处输入图像描述

如果我们分析

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)

您在这里看到我们实现了 (n^2)/2，即使除以 2 并没有更大的区别。

Shell Sort只不过是通过使用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

于 2019-08-23T03:53:03.117 回答