algorithm - 排序名称和时间复杂度

Question

我“发明”了"new"排序算法。好吧，我明白我无法发明出好东西，所以我试着在维基百科上搜索它，但所有排序算法似乎都不是我的。所以我有三个问题:

1. 这个算法的名称是什么？
2. 为什么很烂？ (最佳、平均和最差时间复杂度)
3. 我能否利用这个想法让它变得更好？

所以，我的算法的想法是:如果我们有一个数组，我们可以计算已排序元素的数量，如果这个数字小于长度的一半，我们可以反转数组以使其更有序。之后我们可以对数组的前半部分和后半部分进行排序。在最好的情况下，我们只需要 O(n) - 如果数组完全按好的或坏的方向排序。我在评估平均和最差时间复杂度时遇到了一些问题。

C# 代码:

    public static void Reverse(int[] array, int begin, int end) {
        int length = end - begin;
        for (int i = 0; i < length / 2; i++)
            Algorithms.Swap(ref array[begin+i], ref array[begin + length - i - 1]);
    }
    public static bool ReverseIf(int[] array, int begin, int end) {
        int countSorted = 1;
        for (int i = begin + 1; i < end; i++)
            if (array[i - 1] <= array[i])
                countSorted++;

        int length = end - begin;
        if (countSorted <= length/2)
            Reverse(array, begin, end);

        if (countSorted == 1 || countSorted == (end - begin))
            return true;
        else
            return false;
    }
    public static void ReverseSort(int[] array, int begin, int end) {
        if (begin == end || begin == end + 1)
            return;
        // if we use if-operator (not while), then array {2,3,1} transforms in array {2,1,3} and algorithm stop
        while (!ReverseIf(array, begin, end)) {
            int pivot = begin + (end - begin) / 2;
            ReverseSort(array, begin, pivot + 1);
            ReverseSort(array, pivot, end);
        }
    }
    public static void ReverseSort(int[] array) {
        ReverseSort(array, 0, array.Length);
    }

P.S.:对不起我的英语。

Answer 1

最好的情况是 Theta(n)，例如，对于排序数组。最坏的情况是 Theta(n^2 log n)。

上限

次要 子问题有一个排序数组，其前面或后面是任意元素。这些是 O(n log n)。如果在前面，我们做 O(n) 的工作，在前半部分解决次要子问题，然后在后半部分解决，然后再做 O(n) 的工作——O(n log n)。如果成功，做 O(n) 工作，对已经排序的前半部分进行排序 (O(n))，在后半部分解决一个次要子问题，做 O(n) 工作，在前半部分解决一个次要子问题，对已经对后半部分进行排序 (O(n))，执行 O(n) 工作 – O(n log n)。

现在，在一般情况下，我们在两半上解决两个主要子问题，然后使用次要调用在枢轴上慢慢交换元素。需要进行 O(n) 次交换，因此主定理的直接应用会产生 O(n^2 log n) 的界限。

下限

对于 k >= 3，我们使用上述分析作为指南递归地构造一个大小为 2^k 的数组 A(k)。糟糕的情况是数组 [2^k + 1] + A(k)。

令 A(3) = [1, ..., 8]。这种排序的基本情况使 Reverse 不被调用。

对于 k > 3，令 A(k) = [2^(k-1) + A(k-1)[1], ..., 2^(k-1) + A(k-1 )[2^(k-1)]] + A(k-1)。请注意，[2^k + 1] + A(k) 的主要子问题等同于 [2^(k-1) + 1] + A(k-1)。

在主要递归调用之后，数组是 [2^(k-1) + 1, ..., 2^k, 1, ..., 2^(k-1), 2^k + 1 ].有 Omega(2^k) 个元素必须移动 Omega(2^k) 个位置，到目前为止移动元素的每个二次调用都有 O(1) 个排序的子问题，因此是 Omega(n log n)。

---

显然需要更多的咖啡——主要的子问题并不重要。这使得分析平均情况(也是Theta(n^2 log n))并不太糟糕。

以常数概率，数组的前半部分至少包含最小四分位数的一半和最大四分位数的至少一半。在这种情况下，无论 Reverse 是否发生，都有 Omega(n) 元素必须通过二次调用移动 Omega(n) 位置。