如何检查对 ArrayList 中的元素进行排序需要多少遍？

Question

如何查看使用冒泡排序对arraylist中的元素进行排序需要多少遍？我有这两种方法。

public boolean checkInSortedOrder(ArrayList<QuakeEntry> quakes){
  boolean sorted = true;        
  for (int i = 1; i < quakes.size(); i++) {
            if (quakes.get(i-1).compareTo(quakes.get(i)) > 0){ 
            sorted = false;
        }
}

return sorted;

上述方法检查arrayList 是否已排序。此方法执行冒泡排序。

public void onePassBubbleSort(ArrayList<QuakeEntry> quakeData, int numSorted){
    int j;
    QuakeEntry temp;
  for(int i=0; i<numSorted; i++){
   for( j=0; j<(quakeData.size()-i-1);j++){
         if(quakeData.get(j).getMagnitude()>quakeData.get(j+1).getMagnitude()){
          temp=quakeData.get(j);
          quakeData.set(j,quakeData.get(j+1));
          quakeData.set(j+1,temp);
         }
       } 
      System.out.println("Printing Quakes after "+ i +" pass ");
       for (QuakeEntry qe: quakeData) { 
       System.out.println(qe);
    }
   }

}

我知道我需要添加一个计数器变量。但是有点混淆代码。

Answer 1

最左边的反转位置和最右边的反转位置为您提供了最坏情况下可能必须经过数组的次数。

当然，也有可能你得到的值是高估的。例如数组可能是这样的情况，在这种情况下你会认为需要 6 遍，而 1 遍就足够了。

2 1 4 5 6 8 7

但是这种方法永远不会低估，我相信在很多情况下高估可能比低估更好。毕竟，你可以在每次通过后都这样做，当你发现没有反转时，你就可以停止了。

第二种方法实际上是使用就地 O(nlogn) 算法对数组进行排序，并找到初始索引和最终索引的最大差异来声明有多少遍必需的。但是，如果您在大多数情况下可以自由使用 O(nlogn)，那么您一开始就会这样做。所以，我假设以这种方式模拟排序也不是一个选项。

如果有关于要排序的数据的其他知识，例如帮助 counting sort 的范围信息，也许这可能会有所帮助。例如，如果您知道元素没有重复并且它们在 [1, N] 范围内，那么您仍然可以模拟排序过程并找出初始索引和最终索引的最大差异以用作重复次数。但是，由于您没有提到这样一组特定的额外信息，因此这可能对您也没有帮助。

简而言之，由于排序模拟和额外信息对您不可用，我建议您使用高估方法，这是一种粗略且未经测试的 Java 实现，如下所示。

public int getNumberOfRepsNecessary(ArrayList<QuakeEntry> quakes){
    int leftmostInversion=-1, rightmostInversion = -1;
    for (int i = 1; i < quakes.size(); i++) {
        if (quakes.get(i-1).compareTo(quakes.get(i)) > 0){ 
            if(leftmostInversion == -1) {
                leftmostInversion = i-1;
            }
            rightmostInversion = i-1;
        }
    }
    if(leftmostInversion == -1)
        return 0;
    return rightmostInversion - leftmostInversion + 1;
}

Answer 2

可以简单地使用布尔值来检查对给定列表进行排序需要多少次最小遍历，如下面的代码所示：

import java.util.*;

public class BubbleSort {

    private static final int TOTAL_ELEMENTS = 5;

    private List < Integer > numbers;
    private boolean isSorted;
    private Random random;

    public BubbleSort () {
        random = new Random ();
        isSorted = true;
        numbers = new ArrayList < Integer > ( TOTAL_ELEMENTS );
        numbers.add ( new Integer ( 1 ) );
        numbers.add ( new Integer ( 2 ) );
        numbers.add ( new Integer ( 3 ) );
        numbers.add ( new Integer ( 4 ) );
        numbers.add ( new Integer ( 5 ) );
    }

    private void performTask () {
        int pass = 1;
        while ( pass <= numbers.size () ) {
            isSorted = true;
            for ( int i = 0; i <= ( numbers.size () - pass - 1 ); ++i ) {
                System.out.println ( "i: " + i + " pass: " + pass + "[ i ]: " + numbers.get ( i ) + " [ i + 1 ]: " + numbers.get ( i + 1 )  );
                if ( numbers.get ( i ).compareTo ( numbers.get ( i + 1 ) ) > 0 )  {
                    System.out.println ( "Entered if clause" );
                    Integer temp = numbers.get ( i );
                    numbers.set ( i, numbers.get ( i + 1 ) );
                    numbers.set ( i + 1,  temp );
                    isSorted = false;
                    display ();
                }
            }
            if ( isSorted ) {
                break;
            }
            ++pass;
        }
        System.out.println ( "Minimum passes: " + pass );
        display ();
    }

    private void display () {
        System.out.println ( "Array content: " );
        for ( Integer number : numbers ) {
            System.out.println ( number.intValue () );
        }
    }

    public static void main ( String [] args ) {
        new BubbleSort ().performTask ();
    }
}

如何检查对 ArrayList 中的元素进行排序需要多少遍？

How to check how many passes are needed to sort the elements in an ArrayList?

java

sorting

arraylist

bubble-sort