如何输出冒泡排序中通过的次数，直到对数组进行排序？

2024-05-19 • 问答

package codeabb;
import java.util.*;

public class Bsort {

    public static void main(String args[]) {

        Scanner in = new Scanner(System.in);
        int num = in.nextInt();
        int arr[] = new int[100];
        int swap = 0;
        int pass = num-1;

        for( int i = 0; i < num; i++) {
            arr[i] = in.nextInt();
        }

        for( int i = 0; i < num-1; i++) {
            pass--;
            for( int j = i+1; j < num; j++) {
                int temp;
                if(arr[i] > arr[j]) {
                    swap++;

                    temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;

                }


            }



        }



            System.out.print(pass + " "+swap);

    }

}

我正在尝试输出对数组进行排序时的交换次数和通过次数。通过数量是我估计的array-1总数吗？因此，我已对此进行了初始化，并在每次执行交换时都扣除了此费用，因为一旦进行交换，便进行了下一次传递。但是输出不正确。有人可以帮我吗？

除了减少通过次数外，还应为每个外部循环迭代增加通过次数，并且当内部循环中没有交换时，可以中断外部循环。这样，您将获得适当的通过次数。

int pass=0;
for (int i = 0; i < num - 1; i++) {
            boolean swapsMade = false;
            pass++;
            for (int j = i + 1; j < num; j++) {
                int temp;
                if (arr[j] > arr[j+1]) {
                    swap++;
                    swapsMade = true;
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
            if (!swapsMade) {
                break;
            }
        }

也许可视化步骤有助于了解pass和swap的数量。在下面根据您提供的代码段查找示例。

import java.util.Arrays;

public class Bsort {
    public static void main(String args[]) {
        int arr[] = {5,4,3,2,1};
        int swap = 0;
        int pass = 0;
        for (int i = 0; i < arr.length - 1; i++) {
            pass++;
            for (int j = i + 1; j < arr.length; j++) {
                int temp;
                if (arr[i] > arr[j]) {
                    swap++;
                    temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                    System.out.printf("pass: %02d   swap: %02d  array: %s%n",pass,swap,Arrays.toString(arr));
                }
            }
        }
    }
}

输出

通过：01交换：01数组：[ 4、5 ，3、2、1]
  通过：01交换：02数组：[ 3 ，5， 4 ，2、1]
  通过：01交换：03数组：[ 2 ，5、4， 3 ，1]
  通过：01交换：04数组：[ 1 ，5、4、3， 2 ]

通过：02交换：05数组：[1， 4、5 ，3、2]
  通过：02交换：06数组：[1， 3 ，5， 4 ，2]
  通过：02交换：07数组：[1， 2 ，5，4， 3 ]

通过：03交换：08数组：[1、2， 4 ， 5 ，3]
  通过：03交换：09数组：[1、2， 3 ，5， 4 ]

通过：04交换：10个数组：[1、2、3， 4、5 ]

如何输出冒泡排序中通过的次数，直到对数组进行排序？

vera0101 回答：如何输出冒泡排序中通过的次数，直到对数组进行排序？

大家都在问