計算排序算法的比較次數，並將其添加到java中的數組列表中

嗨，我有一個通用的氣泡排序算法，我正在使用，我想跟蹤數組排序之前發生的比較次數。比較次數必須存儲在數組列表中。我不太確定如何做到這一點，所以我想知道是否有人可以提供幫助。謝謝計算排序算法的比較次數，並將其添加到java中的數組列表中

protected static ArrayList<Integer> noOfComparisons = new ArrayList<Integer>(); 

public static <E extends Comparable<? super E>> void bubbleSort(E[] comparable) { 
boolean changed = false; 
do { 
    changed = false; 
    for (int a = 0; a < comparable.length - 1; a++) { 
     if (comparable[a].compareTo(comparable[a + 1]) > 0) { 
      E tmp = comparable[a]; 
      comparable[a] = comparable[a + 1]; 
      comparable[a + 1] = tmp; 
      changed = true; 
     } 
    } 
} while (changed); 
}

來源

2012-02-02 Matt9Atkins

不清楚ArrayList應該包含什麼 - 整個排序的比較數量？在相應索引處對元素進行比較的次數是多少？ – 2012-02-02 22:47:49

爲什麼你需要將比較次數存儲在一個'ArrayList'中，如果你說它是一個「數字」的比較，你應該能夠將它存儲在一個數字中，比如說類型爲'int' – ggreiner 2012-02-02 22:48:10

你爲什麼要將它存儲在一個'ArrayList'而不是一個'int'中？這是功課嗎？你試過什麼了？ – templatetypedef 2012-02-02 22:48:19

您將需要跟蹤每次對數組進行排序時的比較次數。爲此，請在bubbleSort方法的開始處創建一個初始化爲零的int，然後在執行比較時增加該數字。在你的bubbleSort方法結束時，將該int添加到列表中。

來源

2012-02-02 22:54:47 ggreiner

好的答案，我試圖創建一個方程，但我堅持下去......事實證明，只基於陣列它並不那麼容易確定需要對其進行排序需要多少操作。 – 2012-02-02 22:57:14

沒錯，問題更多的是根據計數*進行比較的次數，而不是預測*基於數組的數字，這會更復雜。 – ggreiner 2012-02-02 22:59:37

我知道，這個方程只是爲了娛樂，並且當有人知道算法的工作原理時，這個問題的答案很簡單。但事實證明，這是一個非常好的數學問題來解決。如果在O（n）時間內有可能計算出我們需要使用冒泡排序對數組進行排序需要多少次操作。 – 2012-02-02 23:04:14

計算排序算法的比較次數，並將其添加到java中的數組列表中

回答

相關問題