如何改进已经是 O(n) 的递归排序算法？

Question

我有一个用于作业的递归排序算法，我的老师说有一种 easy 方法可以提高我算法的运行时间......但我根本无法弄清楚它是什么。除非我弄错了，否则算法的复杂度是 O(n)？我不确定，因为我们在 class 中没有学习如何计算递归方法的复杂度。这是代码：

public static void MyAlgorithm(int[] A, int n){
    boolean done = true;
    int j = 0;
    while (j <= n - 2){
        if (A[j] > A[j + 1]) {
            swap(A,j,j+1);
            done= false;
        }
        j++;
    }
    j = n - 1;
    while (j >= 1){
        if (A[j] < A[j - 1]) {
            swap(A,j-1,j);
            done=false;
        }
        j--; 
    }

    if (!done)
        MyAlgorithm(A, n);
    else
        return;
}

我唯一能想到的就是添加一个 if(done) return;在第一个循环之后，但它只使程序免于执行一些其他操作。哦，交换方法基本上就是：

public static void swap(int[] arr, int pos1, int pos2){
    int temp = arr[pos1];
    arr[pos1] = arr[pos2];
    arr[pos2] = temp;
}

提前谢谢你。

Answer 1

首先，无法使用比较在 O(n) 中执行任何排序算法。作为一般规则，所有排序算法至少需要 O(n*log(n)) 时间。

您使用的排序似乎类似于调酒器排序或双向冒泡排序。它在 O(n^2) 时间内运行。你绝对应该研究你使用的方法并考虑你为什么使用它们，还应该学习如何用大 O 符号正确分类事物。

我想你的老师的意思是你应该将排序称为 MyAlgorithm(a, n-1)。请注意在您的第一个循环中它是如何遍历整个数组的？这意味着当该循环退出时，最后一个元素将已经排序。同样，您可以添加一个起始索引并每次递增它。例如修改后的代码：

public static void MyAlgorithm(int[] A, int start, int n){
    boolean done = true;
    int j = start;
    while (j <= n - 2){
        if (A[j] > A[j + 1]) {
            swap(A,j,j+1);
            done= false;
        }
        j++;
    }
    j = n - 1;
    while (j >= start+1){
        if (A[j] < A[j - 1]) {
            swap(A,j-1,j);
            done=false;
        }
        j--; 
    }

    if (!done)
        MyAlgorithm(A, start+1, n-1);
    else
        return;
}

然后你可以调用它：MyAlgorithm(my_array, 0, my_array.length)

请记住，这仍然不是一个很棒的排序算法，如果您需要对大量数据进行排序，您应该考虑使用更快的算法。

如何改进已经是 O(n) 的递归排序算法？

How to improve a recursive sorting algorithm that is already O(n)?

java

sorting

recursion

big-o

time-complexity