通过用另一个函数替换递归之一来优化排序算法

Question

目前我有这样的排序算法：

public static void sort(int[] A, int i, int j) {
    if (i == j) return;
    if(j == i+1) {
        if(A[i] > A[j]) {
            int temp = A[i];
            A[i] = A[j];
            A[j] = temp;
        }
    } 
    else {
        int k = (int) Math.floor((j-i+1)/3);
        sort(A,i, j-k);
        sort(A,i+k, j);
        sort(A,i,j-k);
    }
}

排序正确，但是，渐近比较相当高：T(n) = 3T(n-f(floor(n/3)) 和 f(n) = theta(n^(log( 3/2)3)

因此，我目前正在考虑将第三个递归sort(A,i,j-k)替换为新编写的迭代方法来优化算法。但是，我不太确定如何解决这个问题，并且很想收集一些想法。谢谢！

Answer 1

如果我理解正确，您首先对列表的前 2/3 进行排序，然后对最后 2/3 进行排序，然后再次对前 2/3 进行排序。这实际上是有效的，因为任何错放的项目（第一个或最后 2/3 中的项目实际上属于最后一个或前 1/3）将被移动，然后在算法的下一次传递中正确排序。

肯定有两点可以优化：

在最后一步中，前 1/3 和后 1/3（因此要排序的区域的前半部分和后半部分）已经按排序顺序排列，因此无需进行完整排序，您可以只使用 merge-algorithm，在 O(n)
不是排序第一个和最后一个 2/3，然后将重叠的元素合并到前 1/3，如上所述，您可以排序前 1/2 和最后 1/2，然后合并这些部分，不重叠；处理的数组总长度相同（2/3 + 2/3 + 2/3 与 1/2 + 1/2 + 2/2），但 merging-part 会比 sorting-part

然而，在第二次“优化”之后，你实际上会或多或少 re-invented Merge Sort。

通过用另一个函数替换递归之一来优化排序算法

Optimizing a sorting algorithm by replacing the one of the recursion with a another function

sorting

algorithm

complexity-theory