为什么我的气泡排序算法比我的程序中选择和插入排序算法更快？

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引入的其他噪声），而不是性能。让你的算法认真工作，如果你想比较它们。