java - 计数循环和比较

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 次传递。

我不确定这个理论是否对你有帮助。请向我提供一些关于您仍然遇到问题的反馈，我会看看是否可以更改我的答案以更好地反射(reflect)您的需求。