计数循环和比较

Question

我需要计算在四种不同的排序方法上发生的循环次数和比较次数。我正在使用“选择”，“泡泡”，“插入”和“快速排序”方法。理想情况下，每次循环/比较时，我只需放置一个int，如loopCounter和++。虽然对于所有这些方面来说都很新颖，但我在区分需要包含这些计数器时遇到了困难。正如你将能够看到下面的代码，我试图创建多个计数器。尽管如此，我认为目前为止只有选拔计数是正确的。

此外，我需要计算一个值转移的次数。换句话说，整数交换了多少次。

任何与此有关的帮助将不胜感激！

感谢

ArrayList<Integer> list = new ArrayList<Integer>(); 

    //Counters for Selection Sort 
    int loopCounter = 0; 
    int compCounter = 0; 
    //Counters for Bubble Sort 
    int loopCounter2 = 0; 
    int compCounter2 = 0; 
    //Counters for Insertion Sort 
    int loopCounter3 = 0; 
    int compCounter3 = 0; 
    //Counters for Quick Sort 
    int loopCounter4 = 0; 
    int compCounter4 = 0; 

public void selectionSort(Integer[] a) { 

    for(int i = 0; i < a.length; i++) { 
     int smallestValue = a[i]; 
     int smallestIndex = i; 
     if(ascButton.isSelected()){ 
      for(int j = i+1; j < a.length; j++) { 
       if (smallestValue > a[j]) { 
        smallestValue = a[j]; 
        smallestIndex = j; 
        loopCounter++; 
        compCounter++; 
       } 
      } 
     a[smallestIndex] = a[i]; 
     a[i] = smallestValue; 
     } else if(desButton.isSelected()){ 
      for(int j = i+1; j < a.length; j++) { 
       if (smallestValue < a[j]) { 
        smallestValue = a[j]; 
        smallestIndex = j; 
        loopCounter++; 
        compCounter++; 
       } 
     } 
     a[smallestIndex] = a[i]; 
     a[i] = smallestValue; 
     } 
    } 
} 

public void bubbleSort(Integer[] a) { 

    int temp; 

    for (int i = a.length - 1; i > 0; i--) { 
     if(ascButton.isSelected()) { 
      for(int j = 0; j < i; j++) { 
       loopCounter2++; 
       compCounter2++; 
       if(a[j] > a[j + 1]) { 
        temp = a[j]; 
        a[j] = a[j + 1]; 
        a[j + 1] = temp; 
       } 
      } 
      } else if(desButton.isSelected()) { 
       for(int j = 0; j < i; j++) { 
        loopCounter2++; 
        compCounter2++; 
        if(a[j] < a[j + 1]) { 
         temp = a[j]; 
         a[j] = a[j + 1]; 
         a[j + 1] = temp; 
        } 
       } 
      } 

    } 
} 

public void insertionSort(Integer[] a) { 
    for(int i = 1; i < a.length; i++) { 
     loopCounter3++; 
     compCounter3++; 
     int temp = a[i]; 
     int j = i - 1; 

     if(ascButton.isSelected()) { 
      while(j >= 0 && a[j] > temp) { 
      a[j + 1] = a[j]; 
      j--; 
     } 
     a[j + 1] = temp; 
     } else if(desButton.isSelected()) { 
      while(j >= 0 && a[j] < temp) { 
      a[j + 1] = a[j]; 
      j--; 
     } 
     a[j + 1] = temp; 
     } 

    } 
} 

public void quickSort(Integer[] a, int left, int right) { 
    int i = left; 
    int j = right; 
    int temp; 
    int pivot = a[(left + right)/2]; 
    while(i <= j) { 
    if(ascButton.isSelected()) { 
     while(a[i] < pivot) 
      i++; 
     while(a[j] > pivot) 
      j--; 
    } else if(desButton.isSelected()) { 
     while(a[i] > pivot) 
      i++; 
     while(a[j] < pivot) 
      j--; 
    } 
     if(i <= j) { 
      temp = a[i]; 
      a[i] = a[j]; 
      a[j] = temp; 
      i++; 
      j--; 
     } 
    } 
    if(left < j) { 
     quickSort(a,left,j); 
    } 
    if(i < right) { 
     quickSort(a, i, right); 
    }    
} 

Answer 1

设有专柜，你只是想“计数”时，要编算什么。所以如果你不明白你自己的代码，那么很难知道你什么时候需要“计数”什么。我建议你找出当交换正在发生的事情，当在代码中发生的事情，那就是当你想要做某种：

swapCount++;//Each time a swap happens increment by 1 
    iterationCount++//A full pass has happened increment by 1 

注：以上只是因为全通已经在许多类型的发生，你可能知道，这并不意味着它是排序的，它只是说它已经完成了1次。

我不确定这个理论是否会帮助你。给我一些关于你仍然有问题的反馈，我会看看我是否可以改变我的答案，以更好地反映你的期望。

Answer 2

正如@Andreas所建议的，你的循环和比较计数器是正确的。 就交换计数器而言，可以这样想 - 如果没有临时变量，就不能交换。因此，无论何时涉及临时变量，您都希望增加交换计数器。 作为一个例子，为您快速排序，它应该是这样的：

public void quickSort(Integer[] a, int left, int right) { 
    int i = left; 
    int j = right; 
    int temp; 
    int pivot = a[(left + right)/2]; 
    while(i <= j) { 
    if(ascButton.isSelected()) { 
     while(a[i] < pivot) 
      i++; 
     while(a[j] > pivot) 
      j--; 
    } else if(desButton.isSelected()) { 
     while(a[i] > pivot) 
      i++; 
     while(a[j] < pivot) 
      j--; 
    } 
     if(i <= j) { 
      temp = a[i]; 
      a[i] = a[j]; 
      a[j] = temp; 
      i++; 
      j--; 
      swapCounterForQuickSort++; 
     } 
    } 
    if(left < j) { 
     quickSort(a,left,j); 
    } 
    if(i < right) { 
     quickSort(a, i, right); 
    }    
} 

按照您的其他类型相同的逻辑。

此外，一些一般性建议：

• 始终名字的变量，让他们告诉你他们使用的东西。而不是loopCounter1尝试使用loopCounterForSelectionSort等。不要害怕长变量名称。信息就是力量！
• 使您的功能尽可能短而且可重用。例如，你在代码中交换整数。也许你可以复制交换代码并将其粘贴到swapIntegers（）函数中。然后每当你想交换的时候你就调用这个函数！此外，请注意这是如何使您的交换计数器问题更容易回答的，因为您可以在交换方法中设置一个计数器来为您计数。 （虽然请注意，因为多个方法会调用swap计数器，因此您可能想将它作为参数传递等）。