java - 选择排序和冒泡排序——如何统计比较次数和交换次数?

标签 java sorting bubble-sort

首先,我看到了一个与 C++ 相关的类似问题,但我不太理解它 - 而且我的问题是关于 Java 的。

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

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

冒泡排序方法:

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;
    }

选择排序方法

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;
    }

最佳答案

对于冒泡排序:

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

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

对于选择排序:

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

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

(注意n是你数组大小的个数)

关于java - 选择排序和冒泡排序——如何统计比较次数和交换次数?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15541963/

相关文章:

java - 使用特殊参数从 Ant 构建文件运行 GWT?

ruby-on-rails - 如何在 ruby​​ on rails 中按日期对二维数组(2d 数组)进行排序?

c# - C++等效于C#Array.Sort

Python:如何使冒泡排序的实现更加省时?

java - 编辑文本到整数 (Android)

java - RMI Java 中服务器对象、远程对象是什么意思?

Java Web 服务指示属性的需求级别

javascript - 基于 javascript 文本的游戏和对象

c++ - 二进制 '[' : no operator found which takes a left hand operand of type 'const SortableVector<int>'

C 链表冒泡排序逻辑错误