java - 如何改进已经是 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) 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)

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