爲什麼在實踐中插入排序比Bubble Sort和堆排序更快？

我在鏈接（http://bigocheatsheet.com/）中看到插入排序的複雜性與冒泡排序相同，並且堆排序也比這兩個更好。但是當我創建一個示例程序並比較了插入排序所花費的時間令人難以置信。爲什麼在實踐中插入排序比Bubble Sort和堆排序更快？

類用於測試排序算法。

public class TestSorts { 

    public static void main(String[] args) { 
     System.out.println("starting"); 
     Calendar startInstance = null; 
     Calendar endInstance = null; 

     //Getting the array to sort 
     startInstance= Calendar.getInstance(); 
     //int[] arrayToSort = ArrayClass.getArray(1000); 
     int[] arrayToSort = ArrayClass.getWorstArray(10000000); 
     endInstance= Calendar.getInstance(); 
     long timeTakenToGetArray = endInstance.getTimeInMillis()- startInstance.getTimeInMillis(); 
     System.out.println("StartTime : "+startInstance.getTimeInMillis()); 
     System.out.println("EndTime : "+endInstance.getTimeInMillis()); 
     System.out.println("TimeTakenToGetArray : "+timeTakenToGetArray); 

     //Bubble Sort  
     startInstance= Calendar.getInstance(); 
     int[] bubbleSorted = BubbleSort.sort(arrayToSort); 
     endInstance= Calendar.getInstance(); 
     long timeTakenBubble = endInstance.getTimeInMillis() - startInstance.getTimeInMillis(); 
     System.out.println("StartTime : "+startInstance.getTimeInMillis()); 
     System.out.println("EndTime : "+endInstance.getTimeInMillis()); 
     System.out.println("Bubble : "+timeTakenBubble); 

     //InsertionSort 
     startInstance= Calendar.getInstance(); 
     int[] insertionSorted = InsertionSort.sort(arrayToSort); 
     endInstance= Calendar.getInstance(); 
     long timeTakenInsertion = endInstance.getTimeInMillis() - startInstance.getTimeInMillis(); 
     System.out.println("StartTime : "+startInstance.getTimeInMillis()); 
     System.out.println("EndTime : "+endInstance.getTimeInMillis()); 
     System.out.println("Insertion : "+timeTakenInsertion); 

     //HeapSort 
     startInstance= Calendar.getInstance(); 
     int[] heapSorted = HeapSort.sort(arrayToSort); 
     endInstance= Calendar.getInstance(); 
     long timeTakenHeap = endInstance.getTimeInMillis() - startInstance.getTimeInMillis(); 
     System.out.println("StartTime : "+startInstance.getTimeInMillis()); 
     System.out.println("EndTime : "+endInstance.getTimeInMillis()); 
     System.out.println("Heap : "+timeTakenHeap); 

     startInstance= Calendar.getInstance(); 
     arraysAreEqual(bubbleSorted, insertionSorted, heapSorted); 
     endInstance= Calendar.getInstance(); 
     long timeTakenToCompare = endInstance.getTimeInMillis() - startInstance.getTimeInMillis(); 
     System.out.println("StartTime : "+startInstance.getTimeInMillis()); 
     System.out.println("EndTime : "+endInstance.getTimeInMillis()); 
     System.out.println("TimeTakenToCompare : "+timeTakenToCompare); 

    } 



    //Method to compare whether the sorted arrays are equal 
    static void arraysAreEqual(int[] bubbleSorted,int[] insertionSorted,int[] heapSorted) 
    { 
     for(int i =0;i<bubbleSorted.length;i++) 
     { 
      if((bubbleSorted[i]!=insertionSorted[i])||(heapSorted[i]!=insertionSorted[i])||(heapSorted[i]!=bubbleSorted[i])) 
      { 
       System.out.println("Bubble : "+bubbleSorted[i]); 
       System.out.println("Insertion : "+insertionSorted[i]); 
       System.out.println("Heap : "+heapSorted[i]); 
      } 
     } 
    } 


}

類爲冒泡排序

public class BubbleSort { 

    static int[] sort(int[] arrayToSort) 
    { 
     int length = arrayToSort.length; 
     for(int i = 0;i<length;i++) 
     { 
      for(int j = i+1;j<length;j++) 
      { 
       if(arrayToSort[i]>arrayToSort[j]) 
       { 
        arrayToSort[i]+=arrayToSort[j]; 
        arrayToSort[j] = arrayToSort[i] - arrayToSort[j]; 
        arrayToSort[i] = arrayToSort[i] - arrayToSort[j]; 
       } 
      } 
     } 

     return arrayToSort; 
    } 

}

類插入排序

public class InsertionSort { 

    static int[] sort(int[] arrayToSort) 
    { 
     for (int i = 0; i < arrayToSort.length; i++) { 
       int value = arrayToSort[i]; 
       int j = i - 1; 
       while (j >= 0 && arrayToSort[j] > value) { 
        arrayToSort[j + 1] = arrayToSort[j]; 
       j = j - 1; 
       } 
       arrayToSort[j + 1] = value; 

       } 
     return arrayToSort; 
    } 

}

類爲堆排序

public class HeapSort { 

    static int a[]; 
    static int[] sort(int[] arrayToSort) 
    { 
     a = arrayToSort; 

     heapsort(); 
     return a; 
    } 
    static void heapsort() 
    { 

     int size = a.length; 
     maxHeapify(size); 
     for(int i =a.length-1;i>=1;i--) 
     { 
      swap(0,i); 
      size--; 
      maxHeapify(size); 
     } 
    } 
    static void maxHeapify(int size) 
    { 
     for(int i =size/2-1;i>=0;i--) 
     { 
      heapify(i,size); 
     } 
    } 


    static void heapify(int i,int size) 
    { 
     int left = 2*i+1; 
     int right = 2*i+2; 
     int max = i; 
     if(left<size&&a[left]>a[i]) 
     { 
      max = left; 
     } 
     if(right<size&&a[right]>a[max]) 
     { 
      max = right; 
     } 
     if(max!=i) 
     { 
      swap(i,max); 
      heapify(max,size); 
     } 

    } 
    static void swap(int i,int j) 
    { 
     int temp = a[i]; 
     a[i] = a[j]; 
     a[j] = temp; 
    } 

}

創建數組

import java.util.Random; 


public class ArrayClass { 

    public static int[] getArray(int size) 
    { 
     int array[] = new int[size]; 

     for(int i =0;i<size;i++) 
     { 
      int s = randomInt(10,size); 

      array[i] = s; 

     } 

     return array; 
    } 

    private static int randomInt(int min,int max) 
    { 
     Random rn = new Random(); 

     int randomNumber = rn.nextInt((max - min) + 1) + min; 

     return randomNumber; 
    } 

    public static int[] getBestArray(int size) 
    { 
     int array[] = new int[size]; 
     for(int i =0;i<size;i++) 
     { 
      array[i]=i+1; 
     } 
     return array; 

    } 
    public static int[] getWorstArray(int size) 
    { 
     int array[] = new int[size]; 
     for(int i =size-1;i>0;i--) 
     { 
      array[i]=i; 
     } 
     return array; 

    } 

}

我試着像最好的情況，最壞的情況和平均情況下，所有場景的類。但是在所有情況下，與泡泡和堆排序相比，插入排序要快得多。理論上堆排序應該是最糟糕的情況下最好的。

當我使用100000作爲最差情況下的輸入時，請找到以下測試結果。

starting 
StartTime : 1413470225347 
EndTime : 1413470225362 
TimeTakenToGetArray : 15 
StartTime : 1413470225362 
EndTime : 1413470226894 
Bubble : 1532 
StartTime : 1413470226894 
EndTime : 1413470226896 
Insertion : 2 
StartTime : 1413470226896 
EndTime : 1413470233474 
Heap : 6578 
StartTime : 1413470233474 
EndTime : 1413470233488 
TimeTakenToCompare : 14

你能告訴我爲什麼插入排序比堆排序更快的輸出嗎？

來源

2014-10-16 robin

另外，JIT編譯器使用基準測試工具來擊敗基準測試是完全可能的。 – aruisdante 2014-10-16 14:47:12

推薦閱讀：http：//en.wikipedia.org/wiki/Insertion_sort – 2014-10-16 14:47:59

getWorstArray應該做什麼？反向填充不會改變任何內容。 – harold 2014-10-16 14:53:00

有一對夫婦的bug：

你BubbleSort種類的陣列（！到位），那麼你傳遞相同的數組下一個方法（InsertionSort）。
getWorstArray正在返回排序後的數組。在另一個方向運行循環不會改變元素的順序。無論如何，你正在使用一個角落案例（排序，反向排序，無所謂），你的結果會有偏差。
一個不錯的BubbleSort提前終止（如果在掃描過程中沒有交換，它會被排序）。

在這一點上，我會質疑其餘的代碼。錯誤通常集中在一起（糟糕的一天，沒有經驗的程序員......）。檢查更多的錯誤。做單元測試。

來源

2014-10-16 14:48:56

BubbleSort對於排序數組是O（n）。 – 2014-10-16 14:50:25

@HunterMcMillen當BubbleSort看到它時，數組未被排序。它按照InsertionSort獲取它的時間排序。因此，BubbleSort在時間上沒有優勢，而InsertionSort則獲得了收益。 – pjs 2014-10-16 14:52:57

修改了所有的評論。 – 2014-10-16 15:00:21

您的排序方法實際上是對原始數組進行排序，而對於已排序的列表，InsertionSort爲O（n）。既然你先做BubbleSort，你已經給了InsertionSort一個不公平的優勢。

爲了更公平的比較，您應該製作原始數組的相同副本（時間以外），並將每個排序例程分別複製一份。這樣你就可以用相同的輸入進行頭對頭的比較。

來源

2014-10-16 14:49:06 pjs

插入對於小列表，排序可能比其他排序更快，因爲它們將每個項目放置在第一次迭代（循環）中的正確位置。減慢速度的方法是將所有事情都轉移到插入的方式上。這就是爲什麼列表必須很小。

來源

2014-10-16 15:18:46 Humpity

爲什麼在實踐中插入排序比Bubble Sort和堆排序更快？

回答

相關問題