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

Question

我有一个用于作业的递归排序算法，我的老师说有一个简单的方法可以提高我的算法的运行时间...但是我根本不知道它是什么。除非我错了，否则算法的复杂度是O（n）？我不确定，因为我们没有在课堂上学习如何计算递归方法的复杂度。代码如下：

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）返回；在第一个循环之后，但它只会使程序免于执行其他一些操作。哦，交换方法基本上就是：

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\u array，0，my\u array.length）调用它

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