如何改進已經是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）

請記住，這仍是一個夢幻般的排序算法，如果你需要對大量數據進行排序，您應該考慮更快地使用某些內容。