创建计算交换和比较的选择排序器时遇到问题

Question

我在尝试计算 Java 中使用选择排序的 int 数组的交换和比较次数时遇到了问题。我对循环中交换和比较计数的位置感到困惑。任何指导将不胜感激。

    public class IntSelectionSorter {

public static int count = 0;
public static int count2 = 0;

public static void selectionSort(int[] array)
{
    int startScan;
    int index;
    int minIndex;
    int minValue;

    for (startScan = 0; startScan < (array.length - 1); startScan++)
    {
        minIndex = startScan;
        minValue = array[startScan];

        for (index = startScan + 1; index < array.length; index++)
        {
            count2++;
            if (array[index] < minValue)
            {
                minValue = array[index];
                count++;
                minIndex = index;
            }
        }
        array[minIndex] = array[startScan];
        count++;
        array[startScan] = minValue;
        count++;
    }
}

}

Answer 1

count2 似乎是正确的。计数应更改如下：

for (startScan = 0; startScan < (array.length - 1); startScan++)
{
    minIndex = startScan;
    minValue = array[startScan];

    for (index = startScan + 1; index < array.length; index++)
    {
        count2++;
        if (array[index] < minValue)
        {
            minValue = array[index];
            // count++; delete this
            minIndex = index;
        }
    }
    if (minIndex != startScan) {
        array[minIndex] = array[startScan];
        count++;
        array[startScan] = minValue;
    }
}

基本上，仅当需要交换时才增加计数，即当 startScan 之后的数组中有另一个数字小于 startScan 时的值。

Answer 2

public class 排序测试 {

public static void main(String[] args) 
{
    int[] values = { 1,53,86,21,49,32,90,65,33,11,34,68,54,32,78,80,35,22,96,59,265,44324,123,3123,25435};

    System.out.println("Original Order: ");
    for (int element : values) 
        System.out.print(element + " ");

    IntBubbleSorter.bubbleSort(values);

    System.out.println("\nSorted order: ");
    for (int element : values) 
        System.out.print(element + " ");

    System.out.println();

    System.out.print("\n Bubble Sort Swaps:" + IntBubbleSorter.count);
    System.out.print("\n Bubble Sort Comparisons:" + IntBubbleSorter.count2);

    System.out.println();

    System.out.println("\nOriginal Order: ");
    for (int element : values) 
        System.out.print(element + " ");

    IntSelectionSorter.selectionSort(values);

    System.out.println("\nSorted order: ");
    for (int element : values) 
        System.out.print(element + " ");

    System.out.println();

    System.out.print("\n Selection Sort Swaps:" + IntSelectionSorter.count);
    System.out.print("\n Selection Sort Comparisons:" + IntSelectionSorter.count2);

    System.out.println();

    System.out.println("\nOriginal Order: ");
    for (int element : values) 
        System.out.print(element + " ");

    IntInsertionSorter.insertionSort(values);

    System.out.println("\nSorted order: ");
    for (int element : values) 
        System.out.print(element + " ");

    System.out.println();

    System.out.print("\n Insertion Sort Swaps:" + IntInsertionSorter.count);
    System.out.print("\n Insertion Sort Comparisons:" + IntInsertionSorter.count2);
}

}

创建计算交换和比较的选择排序器时遇到问题

Trouble with creating a Selection Sorter counting swaps and comparisons

java

selection-sort