java SelectionSort 和 BubbleSort - 如何计算比较和数字交换的次数？

SelectionSort and BubbleSort - how to count number of comparisons and number swapping?

提问by Rob

First of all, I have seen a similar question relating to C++, but I didn't quite understand it - plus my question is about Java.

首先，我看到了一个与 C++ 相关的类似问题，但我不太明白——而且我的问题是关于 Java 的。

Basically I have coded two methods that can use SelectionSort and BubbleSort on an array parsed in. While I believe I have the methods working correctly (I have run tests and they all have sorted the numbers in ascending order), I am not sure if I am counting the number of comparisons and number swaps correctly. If someone is able to test my code below and offer some feedback, I will be very grateful.

基本上我已经编写了两种可以在解析的数组上使用 SelectionSort 和 BubbleSort 的方法。虽然我相信我的方法工作正常（我已经运行测试并且它们都按升序对数字进行了排序），但我不确定我是否我正在正确计算比较和数字交换的次数。如果有人能够测试我下面的代码并提供一些反馈，我将不胜感激。

Note: I can zip up my Java project files and send them to anyone if needed.

注意：如果需要，我可以压缩我的 Java 项目文件并将它们发送给任何人。

BubbleSort method:

冒泡排序方法：

public String bubbleSort(int[] numbers)
    {
        System.out.println("******|Bubble Sort|******");
        StringBuilder originalArray = new StringBuilder();

        for(int i = 0; i <= numbers.length - 1; i++)
        {
            originalArray.append(numbers[i] + " ");
        }
        System.out.println("Original array: " + originalArray);
        int temp; // temporary variable

        //Set boolean variable to true, 
        //to allow the first pass.
        boolean pass = true;

        int comparisons = 0;
        int swaps = 0;

        //While a pass can be made, 
        while(pass)
        {
            //Set the boolean value to false, 
            //indicating a number swap could 
            //be made.
            pass = false;

            for(int i = 0; i < numbers.length - 1; i++)
            {
                //increment the number of comparisons by 1.
                comparisons++;
                if(numbers[i] > numbers[i+1])
                {
                    temp = numbers[i];
                    numbers[i] = numbers[i + 1];
                    numbers[i+1] = temp;

                    //increment the amount of swaps made by 1, 
                    //to put numbers in correct order.
                    swaps++;
                    pass = true;
                }
            }
        }

        //Create a StringBuilder object - to hold 
        //the output of sorted numbers.
        StringBuilder sb = new StringBuilder();

        //Loop through the now sorted array - appending 
        //each subsequent number in the array to the 
        //StringBuilder object.
        for(int i = 0; i < numbers.length; i++)
        {
            sb.append(numbers[i] + " ");
        }

        //Return the final results of the sorted array.
        return "Sorted Array (asc): " + sb.toString() + "\nComparisons made: " + comparisons 
                + "\nSwaps made: " + swaps;
    }

SelectionSort method

选择排序方法

public String selectionSort(int[] numbers)
    {
        System.out.println("******|Selection Sort|******");
        StringBuilder originalArray = new StringBuilder();

        int comparisons = 0;
        int swaps = 0;

        for(int i = 0; i <= numbers.length - 1; i++)
        {
            originalArray.append(numbers[i] + " ");
        }
        System.out.println("Original array: " + originalArray);

        //Declare variable to hold first element
        int first;

        //declare temporary variable, to be used in 
        //swapping integers.
        int temp;

        for(int x = numbers.length - 1; x > 0; x--)
        {
            first = 0;
            comparisons++;
            for(int y = 1; y <= x; y++)
            {
                //comparisons++;
                if(numbers[y] > numbers[first])
                {
                    first = y;
                    //comparisons++;
                    swaps++;
                }
                temp = numbers[first];
                numbers[first] = numbers[x];
                numbers[x] = temp;
                //swaps++;
            }
        }

        //Create a StringBuilder object - to hold 
        //the output of sorted numbers.
        StringBuilder sb = new StringBuilder();

        //Loop through the now sorted array - appending 
        //each subsequent number in the array to the 
        //StringBuilder object.
        for(int i = 0; i < numbers.length; i++)
        {
            sb.append(numbers[i] + " ");
        }

        //Return the final results of the sorted array.
        return "Sorted Array (asc): " + sb.toString() + "\nComparisons made: " + comparisons 
                + "\nSwaps made: " + swaps;
    }

回答by Jessekiel Ragos

For BUBBLE SORT:

对于冒泡排序：

Key comparisons ->(n*(n-1))/2

关键比较 -> (n*(n-1))/2

Item assignments (swaps) ->3*(n-1)

项目分配（交换）-> 3*(n-1)

For SELECTION SORT:

对于选择排序：

Key comparisons ->(n*(n-1))/2(same as bubble)

关键比较 -> (n*(n-1))/2（与气泡相同）

Item assignments (swaps) ->(n*(n-1))/4

项目分配（交换）-> (n*(n-1))/4

(Note that nis the number of your array size)

（请注意，n是数组大小的数量）