爲什麼我的氣泡排序算法比我的程序中選擇和插入排序算法更快？

Question

爲什麼我的氣泡排序算法比我的程序中的選擇和插入排序算法更快？

該程序是一個程序，它包含一個網格，並且在網格中，這些列包含必須進行排序的不同數量的數字，並且這些行具有不同的排序算法，用於對點擊的數量進行排序在網格中，算法對排序隨機生成的＃所花費的時間將被打印出來。

//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
int n = 99; 
int min, tmp, i, j, min_id, data, k, temp; 
int[] array = new int [n]; 

//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
void setup() { 

    size(661, 500); 
    background(255); 

    initArr(); 
    bubbleSort(); 
    selectionSort(array, n); 
    insertionSort(array); 
    quickSort(0, n - 1); 
} 

//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
void draw() { 

    drawGrid(); 
    labels(); 
} 

//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
void initArr() { 

    for (i = 0; i < n; i ++) { 
    array[i] = (int)random(1, 10); 
    } 
} 

//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
void mouseReleased() { 
    for (int j = 1; j < 5; j ++) { 

    for (int i = 1; i < 6; i ++) { 

     if (mouseX > i * 110 && mouseX < i * 110 + 110 && mouseY > j * 80 && mouseY < j * 80 + 80) { 
     println("X:" + " " + i + " " + "Y:" + " " + j); 

     if (i == 1 && j == 1) { 
      initArr(); 
      int start = millis(); 
      bubbleSort(); 
      int ellapsed = millis() - start; 
      println("Time:" + " " + (float)ellapsed/1000); 
     } else if (i == 2 && j == 1) { 
      int n = 999; 
      array = new int[n]; // Brand new array. 
      initArr(); 
      int start = millis(); 
      bubbleSort(); 
      int ellapsed = millis() - start; 
      println("Time:" + " " + (float)ellapsed/1000); 
     } else if (i == 3 && j == 1) { 
      int n = 9999; 
      array = new int[n]; // Brand new array. 
      initArr(); 
      int start = millis(); 
      bubbleSort(); 
      int ellapsed = millis() - start; 
      println("Time:" + " " + (float)ellapsed/1000); 
     } else if (i == 4 && j == 1) { 
      int n = 99999; 
      array = new int[n]; // Brand new array. 
      initArr(); 
      int start = millis(); 
      bubbleSort(); 
      int ellapsed = millis() - start; 
      println("Time:" + " " + (float)ellapsed/1000); 
     } else if (i == 5 && j == 1) { 
      int n = 999999; 
      array = new int[n]; // Brand new array. 
      initArr(); 
      int start = millis(); 
      bubbleSort(); 
      int ellapsed = millis() - start; 
      println("Time:" + " " + (float)ellapsed/1000); 
     } else if (i == 1 && j == 2) { 
      initArr(); 
      int start = millis(); 
      selectionSort(array, n); 
      int ellapsed = millis() - start; 
      println("Time:" + " " + (float)ellapsed/1000); 
     } else if (i == 2 && j == 2) { 
      int n = 999; 
      array = new int[n]; // Brand new array. 
      initArr(); 
      int start = millis(); 
      selectionSort(array, n); 
      int ellapsed = millis() - start; 
      println("Time:" + " " + (float)ellapsed/1000); 
     } else if (i == 3 && j == 2) { 
      int n = 9999; 
      array = new int[n]; // Brand new array. 
      initArr(); 
      int start = millis(); 
      selectionSort(array, n); 
      int ellapsed = millis() - start; 
      println("Time:" + " " + (float)ellapsed/1000); 
     } else if (i == 4 && j == 2) { 
      int n = 99999; 
      array = new int[n]; // Brand new array. 
      initArr(); 
      int start = millis(); 
      selectionSort(array, n); 
      int ellapsed = millis() - start; 
      println("Time:" + " " + (float)ellapsed/1000); 
     } else if (i == 5 && j == 2) { 
      int n = 999999; 
      array = new int[n]; // Brand new array. 
      initArr(); 
      int start = millis(); 
      selectionSort(array, n); 
      int ellapsed = millis() - start; 
      println("Time:" + " " + (float)ellapsed/1000); 
     } else if (i == 1 && j == 3) { 
      initArr(); 
      int start = millis(); 
      insertionSort(array); 
      int ellapsed = millis() - start; 
      println("Time:" + " " + (float)ellapsed/1000); 
     } else if (i == 2 && j == 3) { 
      int n = 999; 
      array = new int[n]; // Brand new array. 
      initArr(); 
      int start = millis(); 
      insertionSort(array); 
      int ellapsed = millis() - start; 
      println("Time:" + " " + (float)ellapsed/1000); 
     } else if (i == 3 && j == 3) { 
      int n = 9999; 
      array = new int[n]; // Brand new array. 
      initArr(); 
      int start = millis(); 
      insertionSort(array); 
      int ellapsed = millis() - start; 
      println("Time:" + " " + (float)ellapsed/1000); 
     } else if (i == 4 && j == 3) { 
      int n = 99999; 
      array = new int[n]; // Brand new array. 
      initArr(); 
      int start = millis(); 
      insertionSort(array); 
      int ellapsed = millis() - start; 
      println("Time:" + " " + (float)ellapsed/1000); 
     } else if (i == 5 && j == 3) { 
      int n = 999999; 
      array = new int[n]; // Brand new array. 
      initArr(); 
      int start = millis(); 
      insertionSort(array); 
      int ellapsed = millis() - start; 
      println("Time:" + " " + (float)ellapsed/1000); 
     } else if (i == 1 && j == 4) { 
      initArr(); 
      int start = millis(); 
      quickSort(0, n - 1); 
      int ellapsed = millis() - start; 
      println("Time:" + " " + (float)ellapsed/1000); 
     } else if (i == 2 && j == 4) { 
      int n = 999; 
      array = new int[n]; // Brand new array. 
      initArr(); 
      int start = millis(); 
      quickSort(0, n - 1); 
      int ellapsed = millis() - start; 
      println("Time:" + " " + (float)ellapsed/1000); 
     } else if (i == 3 && j == 4) { 
      int n = 9999; 
      array = new int[n]; // Brand new array. 
      initArr(); 
      int start = millis(); 
      quickSort(0, n - 1); 
      int ellapsed = millis() - start; 
      println("Time:" + " " + (float)ellapsed/1000); 
     } else if (i == 4 && j == 4) { 
      int n = 99999; 
      array = new int[n]; // Brand new array. 
      initArr(); 
      int start = millis(); 
      quickSort(0, n - 1); 
      int ellapsed = millis() - start; 
      println("Time:" + " " + (float)ellapsed/1000); 
     } else if (i == 5 && j == 4) { 
      int n = 999999; 
      array = new int[n]; // Brand new array. 
      initArr(); 
      int start = millis(); 
      quickSort(0, n - 1); 
      int ellapsed = millis() - start; 
      println("Time:" + " " + (float)ellapsed/1000); 
     } 
     } 
    } 
    } 
} 

//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
void labels() { 

    for (k = 0; k < 5; k ++) { 
    rect(0, k * 80, 110, 80); 
    rect(k * 110 + 110, 0, 110, 80); 
    } 

    for (k = 0; k < 3; k ++) { 
    rect(k * 183.5 + 110, 400, 183.5, 80); 
    } 

    fill(0); 
    text("ALGORITHM", 20, 45); 
    text("BUBBLE", 20, 125); 
    text("SELECTION", 20, 205); 
    text("INSERTION", 20, 285); 
    text("QUICK", 20, 365); 

    text("100", 150, 45); 
    text("1000", 260, 45); 
    text("10000", 365, 45); 
    text("100000", 470, 45); 
    text("1000000", 575, 45); 
} 

//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
void drawGrid() { 

    //----Grid---- 
    for (j = 1; j < 5; j ++) { //columns 
    for (i = 1; i < 6; i ++) { // rows 

     fill(255); 
     if (i != 0 && j != 0 && j <= 4 && i <= 5) { 
     if (mouseX > i * 110 && mouseX < i * 110 + 110 && mouseY > j * 80 && mouseY < j * 80 + 80) 
      fill(255, 200, 200); 
     } else 
     fill(255); 

     rect(i * 110, j * 80, 110, 80); 
    } 
    } 
} 

//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
void bubbleSort() { 

    for (i = 0; i < n - 1; i++) { 
    for (j = 0; j < n - i - 1; j++) 
     if (array[j] > array[j+1]) { 
     temp = array[j]; 
     array[j] = array[j + 1]; 
     array[j + 1] = temp; 
     } 
    } 
} 

//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
void selectionSort (int array[], int n) { 

    for (i = 0; i < n - 1; i ++) { 
    min = array[i]; 
    for (j = i + 1; j < n; j ++) { 
     if (array[j] < min) { 
     min = array[j]; 
     min_id = j; 
     } 
    } 
    tmp = array[i]; 
    array[i] = array[min_id]; 
    array[min_id] = tmp; 
    } 
} 

//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
void insertionSort(int[] array) { 

    for (int i = 1; i < array.length; i++) 
    { 
    // a temporary copy of the current element 
    temp = array[i]; 

    // find the position for insertion 
    for (j = i; j > 0; j--) 
    { 
     if (array[j - 1] < temp) 
     break; 
     // shift the sorted part to right 
     array[j] = array[j - 1]; 
    } 

    // insert the current element 
    array[j] = temp; 
    } 
} 

//- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
void quickSort(int low, int high) { 
    i = low; 
    j = high; 
    // calculate pivot number, I am taking pivot as middle index number 
    int pivot = array[low+(high-low)/2]; // Divide into two arrays 
    while (i <= j) { 
    /** 
    * In each iteration, we will identify a number from left side which 
    * is greater then the pivot value, and also we will identify a number 
    * from right side which is less then the pivot value. Once the search 
    * is done, then we exchange both numbers. 
    */ 
    while (array[i] < pivot) { 
     i++; 
    } 
    while (array[j] > pivot) { 
     j--; 
    } 
    if (i <= j) { 
     temp = array[i]; 
     array[i] = array[j]; 
     array[j] = temp; 
     //move index to next position on both sides 
     i++; 
     j--; 
    } 
    } 
    // call quickSort() method recursively 
    if (low < j) 
    quickSort(low, j); 
    if (i < high) 
    quickSort(i, high); 
} 

Answer 1

你錯過了一些東西出來：

1. 爲使用Java語言編寫的基準是an art on its own由於這樣的事實，除其他外JVM本身是一個軟件相當複雜的一塊，做了相當多的你的代碼優化，重新編譯它等等。
2. 快速排序有asymptotically better runtime（請參閱數學附件this answer）的事實意味着會有一定的保證點，之後它會更快。對於較小的輸入，漸近較差的算法實際上可能是更好的選擇。
3. 您可以以微秒爲單位來測量時間，對於像您一樣小的輸入，分辨率太低。測量的時間不會比隨機噪聲多得多
4. 傳遞給排序函數的輸入的狀態。您的輸入可能或多或少是隨機的，但所有值都在1到10的範圍內。如果您想真正測試您的運行時實現，請給它們輸入更大範圍的值並確保所有函數接收相同輸入。大多數排序算法以特殊方式運行，只要輸入符合某些標準的輸入。例如。正確實施的bubblesort應在O(n)的排序陣列上運行。
5. 最後但並非最不重要的一點是：輸入大小太小而不能使基準有意義。在實現時，最重要的因素是線程調度（以及OS引入的其他噪聲），而不是性能。讓你的算法認真工作，如果你想比較它們。