计算排序算法的比较次数，并将其添加到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中的数组列表中

回答

相关问题