如何確定兩個最快的排序算法？

Question

我有兩種算法。

1.

void sort3(int *mass, int size) 
{ 
    int i = 0; 
    int j = size - 1; 
    int temp; 
    int mid = mass[size/2]; 
    do 
    { 
     while (mass[i] < mid) 
     { 
      i++; 
     } 
     while (mass[j] > mid) 
     { 
      j--; 
     } 
     if (i <= j) 
     { 
      temp = mass[i]; 
      mass[i] = mass[j]; 
      mass[j] = temp; 
      i++; 
      j--; 
     } 
    } while (i <= j); 

    if (j > 0) 
    { 
     sort3(mass, j + 1); 
    } 
    if (i < size) 
    { 
     sort3(&mass[i], size - i); 
    } 
} 

2.

void sort4_prepare(int *mass, int size) 
{ 
    int middle, start_left, start_right, last; 
    int *work_mas = new int[size]; 
    middle = size/2; 
    start_left = 0; 
    start_right = middle; 
    last = size; 
    for (int j = 0; j < last; j++) 
    { 
     if ((start_left < middle) && ((start_right >= last) || (mass[start_left] < mass[start_right]))) 
     { 
      work_mas[j] = mass[start_left]; 
      start_left++; 
     } 
     else 
     { 
      work_mas[j] = mass[start_right]; 
      start_right++; 
     } 
    } 
    for (int j = 0; j < last; j++) 
     mass[j] = work_mas[j]; 
    delete[] work_mas; 
}; 

void sort4(int *mass, int size) 
{ 
    if (size > 1) 
    { 
     sort4(mass, size/2); 
     sort4(&mass[size/2], size - size/2); 
     sort4_prepare(mass, size); 
    } 
} 

我也有從最大排序以最小1000張的隨機數的陣列。哪種算法會將數組從最小值到最大值排序得更快？我做了一些測試，我認爲這是第一個，但我不知道如何證明。但是，在某些情況下，第二個將比第一個更快，這使得我在測試中有點不確定。

Answer 1

sort3是QuickSort的實現，其具有在最壞情況下一個O（N²）時間複雜度，但平均O（nlogn）。

sort4是MergeSort的執行，其性能爲O（nlogn）均處於最差和平均情況。

但是，這並不意味着sort4保證是你的1000個號碼的陣列快，即使在快速排序的最壞的情況。它僅意味着對於陣列的一些類別（快速排序的「最壞情況」的那種陣列），存在的陣列大小高於該sort4會更快。對平均排序任何陣列所需的時間沒有什麼可說的，因爲它們平均具有相同的時間複雜度。此外，您不知道Mergesort在Quicksort的「最差情況」數組上執行得更好，因爲這取決於實現問題：例如，一個編譯器可能以某種方式編譯代碼在sort4的delete操作非常昂貴的在時間上，所以對於大多數合理大小的數組，sort3可能變成是總是更快。這不是牽強附會，事實上，sort4不同之處在於它需要創建一個額外的數組的值複製到sort3，到然後再刪除該陣列。這是sort3沒有的開銷。

唯一可行的方法，以確定是否平均一個功能排序比其他對於給定的數組大小更快，是得到一個統計指標：重複排序操作的次數是代表一些隨機填充陣列，並測量時差。但是這種測試的結果在不同配置下運行時可能會有所不同。