为什么我的基于Java的冒泡排序优于选择排序和插入排序

6

好的,我有一个冒泡排序、选择排序和插入排序的实现。我使用Java.Random对象创建了三个包含一百万个数字的相同数组,并依次将它们传递给每个排序方法。我使用System.nanotime来计时结果。

一些背景信息:我遵循Frank Carano的《Java数据结构与抽象》第三版中提供的选择排序和插入排序算法,冒泡排序是我自己想出来的。

下面我提供了一个自包含的类来执行所有这些操作。我没有看到Carano的算法哪里出错了?

如下所示,我正在计算基本操作的周期数并计时完成时间。在运行时,循环次数几乎没有区别。对于我来说,在看到完成时间时,冒泡排序第一,选择排序第二,插入排序第三。这与常规智慧相悖。为什么?我做了一些愚蠢的事情吗?

顺便说一句,你应该能够编译并运行提供的代码而不需要进行任何更改。

import java.util.Random;


/**
 * 
 * Performs sorts on generic data, here using Integers.
 */
public class GenSorts {

    static int selectionCount = 0, bubbleCount = 0, insertionCount = 0;;

    //=========================================================================
    /**
     * Do an insertion sort.
     * @param data The array to sort
     * @param first The index of the first element
     * @param lasr The index of the last element
     */
    //=========================================================================
    public static <T extends Comparable<? super T>> void insertionSort(T[]array, int first, int last){

        for(int untouch = first + 1; untouch < last; untouch++){
            T nextToInsert = array[untouch];

            insertInOrder(nextToInsert, array, first, untouch-1);

        }//end for
    }//=========================================================================

    //=========================================================================
    /**
     * Performs the shuffle and insert part of the insertion sort.
     * @param anEntry The value to insert
     * @param array The target array
     * @param begin The begin of the unsorted part.
     * @param end The end of the unsorted part.
     */
    //=========================================================================
    public static <T extends Comparable<? super T>> void insertInOrder(T anEntry, T[]array, int begin, int end){

         int index = end;
         //Do a shunt while an entry is less than the value at the index
         while( ( index >= begin )  && (anEntry.compareTo(array[index]) < 0)  ){
             array[index+1] = array[index];
             index --;
             insertionCount++;
         }

         array[index+1] = anEntry;//Insert
    }//======================================================================


    //======================================================================
    /**
     *  BUBBLE SORT///////////////////////////////////////////////////////////
     * Perform a bubble sort on the data.
     * @param data The array to be sorted.
     */
    //======================================================================
    public static <T extends Comparable <? super T> >void bubbleSort  (T[] data)
    {
        Boolean swapped = true;
        int stop = data.length -1;


         while (swapped) {
            swapped = false;

            for (int x = 0; x < stop ; x++ ) {
                 bubbleCount++;
                //if x smaller than x +1 swap
               if ( data[x].compareTo(  data[x+1]   ) > 0 ) { 

                      swap(x, x+1, data );
                      swapped = true;
               }//end if 

               stop --;

           }//end for 

        }//end while
    }//end  method============================================================


    //========================================================================
    /**
     * SELECTION SORT/////////////////////////////////////////////////////////
     * A selection sort algorithm to sort data.
     * @param data
     * @return
     */
    //========================================================================
    public static <T extends Comparable<? super T> >  void selectionSort(T[] data, int n){

         for (int index = 0; index < n - 1; index++)
          {
             selectionCount++;
             int min = getSmallestIndex( index, n,data);

             swap(  index, min, data);

             //DISPLAYME
           //  displaySelectionArray(index, min, data);
          }

    }//========================================================================



    //==========================================================================
    /**
     * Get the index of the smallest item in the array from start to end/
     * @param start The place in the array to start looking.
     * @param end The place in the array to end looking.
     * @param array The array to inspect.
     * @returnThe index of the smallest.
     */
    //==========================================================================
     private static <T extends Comparable<? super T>> int  getSmallestIndex( int start, int end, T[] array)
       {
          T min = array[start];//value of smallest
          int minIndex = start;//index of smallest
          for (int i = start + 1; i < end; i++)
          {

             // System.out.print(array[i].toString() + ", ");
             if (array[i].compareTo(min) < 0)
             {
                minIndex = i;
                min = array[i];
             }//end if
          }//end for

        //  System.out.println("");
          return minIndex;
       }//========================================================================


    //=========================================================================
    /**
     * Swap emelement numbers j and iMin in array data.
     * @param j
     * @param iMin
     * @param data
     */
    //=========================================================================
    public static<T extends Comparable <? super T> > void swap(int j, int iMin, T[]  data){

         T temp = data[j];
         data[j] = data[iMin];
         data[iMin] = temp;
    }//end swap================================================================


    public static Integer[] largeRandom1, largeRandom2, largeRandom3;

    //========================================================================
    /**
     * Generate large integers for sorting.
     * @param n The value of n.
     */
    //========================================================================
    public static void genLargeRandom(int n){
        Random r = new Random();
        largeRandom1 = new Integer[n];
        largeRandom2 = new Integer[n];
        largeRandom3 = new Integer[n];


        for(int i = 0; i < n; i++){
            largeRandom1[i] = r.nextInt(100);
            largeRandom2[i] = largeRandom1[i];
            largeRandom3[i] = largeRandom1[i];
        }//end for
    }//end genLarge//==========================================================

    //=========================================================================
    /**
     * Sort a large numvber.
     * @param args
     */
    //=========================================================================
    public static void main(String[] args){

        genLargeRandom(100000);//one hundred thousand
        Integer[] data = largeRandom1;///{40, 3, 2, 7, 4}; 
        Integer[] data2 = largeRandom2;
        Integer[] data3 =  largeRandom3;


        System.out.println("BUBBLE SORT!!");
        Long t1s = System.nanoTime();
        bubbleSort(data);///////////////Bubble  Sort
        Long t1e = System.nanoTime();

        System.out.println("SELECTION SORT!!");
        Long t2s = System.nanoTime();
        selectionSort(data2, data2.length);///////////////Selection Sort
        Long t2e = System.nanoTime();


        System.out.println("INSERTION SORT!!");
        Long t3s = System.nanoTime();
        insertionSort(data3,0, data3.length);////////////Insertion Sort
        Long t3e = System.nanoTime();


        System.out.println("Bubble Time: " + (t1e - t1s));
        System.out.println("Selection Time: " + (t2e - t2s));
        System.out.println("insertion Time: " + (t3e - t3s));

        System.out.println("Bubble count: " + bubbleCount );
        System.out.println("Selection ccount :" + selectionCount );
        System.out.println("Insertion ccount :" + selectionCount );


    }//========================================================================

}//############################################################################

1
我投票将此问题标记为不适用,因为它属于codereview - Uwe Plonus
请参考以下链接:如何在Java中编写正确的微基准测试 - lance-java
1
为了真正看到这些代码的性能,您应该多次发出排序指令;这里有JIT要考虑。这就是微基准库的用处(JMH、caliper——尽管后者已经有一段时间没有维护了)。 - fge
1
将来,强调冒泡排序比其他算法快多少会很有用。句子“At run time the number of cycles is negligibly different”让人觉得这是JVM细节和微优化的问题。 - user2357112
1
据我所知,这个问题并不适合放在代码审查上。代码审查是用于对工作代码提出建议的,而不是解决问题。 - Radiodef
显示剩余6条评论
1个回答

5
你的冒泡排序出了问题。尝试为一个简单的输入打印结果,你会清楚地看到这一点;例如,尝试对 (3, 2, 1) 进行排序会得到 (2, 3, 1)。你错放了 stop--
public static <T extends Comparable <? super T> >void bubbleSort  (T[] data)
{
    Boolean swapped = true;
    int stop = data.length -1;


     while (swapped) {
        swapped = false;

        for (int x = 0; x < stop ; x++ ) {
             bubbleCount++;
            //if x smaller than x +1 swap
           if ( data[x].compareTo(  data[x+1]   ) > 0 ) { 

                  swap(x, x+1, data );
                  swapped = true;
           }//end if 

           stop --; // needs to go outside the for

       }//end for 

    }//end while
}//end  method============================================================

1
刚刚得出了同样的结论。楼主在开始基准测试之前应该检查他的方法的结果。如果时间差异不是那么大,他甚至都不会注意到。 - Fox
3
啊,哪里有“请那个人吃午餐”的按钮?太晚了,我已经工作了一整晚了。非常感谢你能成为我的第二双眼睛。现在冒泡排序糟糕的程度正如我所期望的那样,真是太棒了!非常感谢。 - Andrew S

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接