排序數組時奇怪的算法性能（編輯）

Question

您好我正在測試排序算法時，排序數組大小爲2500到25000之間的幾個排序算法的性能。我比較的兩種排序是侏儒排序和快速排序，從我讀過的關於這些快速排序的應該會快很多，但侏儒排序在任何情況下都擊敗它。

的快速排序的代碼是：

void myQuickSort(Record sRecord[], int firstElement, int lastElement, bool (*funPoint) (int,int)) 
{ 
int i = firstElement; 
int j = lastElement; 
int temp; 
char tmpname[NAMESIZE]; 


int pivot = sRecord[(firstElement + lastElement)/2].score; 

bool (*myPoint)(int,int) = funPoint; 

while (i <= j) 
{ 
    while (sRecord[i].score < pivot) 
    { 
     i++; 
    } 
    while (sRecord[j].score > pivot) 
    { 
     j--; 
    } 

    if(compareResult(sRecord[j].score,sRecord[i].score) == false) 
    { 
     temp = sRecord[i].score; 
     strcpy(tmpname,sRecord[i].name); 

     sRecord[i].score = sRecord[j].score; 
     strcpy(sRecord[i].name,sRecord[j].name); 

     sRecord[j].score = temp; 
     strcpy(sRecord[j].name, tmpname); 

     i++; 
     j--; 
    } 

    if(firstElement < j) 
    { 
     myQuickSort(sRecord, firstElement, j, compareResult); 
    } 
    if(i < lastElement) 
    { 
     myQuickSort(sRecord, i, lastElement , compareResult); 
    } 
} 
} 

和GnomeSort如下：

void myGnomeSort(Record sRecord[], int size, bool (*funPoint)(int,int)) 
{ 
    int pos = size, temp; 
    char tmpname[NAMESIZE]; 

    bool (*myPoint)(int,int) = funPoint; 

    while(pos > 0) 

    { 

     if (pos == size || myPoint(sRecord[pos].score, sRecord[pos-1].score) == false) 

      pos--; 

     else 
     { 
      temp = sRecord[pos].score; 
      strcpy(tmpname,sRecord[pos].name); 

      sRecord[pos].score = sRecord[pos-1].score; 
      strcpy(sRecord[pos].name,sRecord[pos-1].name); 

      sRecord[pos-1].score = temp; 
      strcpy(sRecord[pos-1].name, tmpname); 

      pos--; 

      } 
    } 
} 

任何人都可以請一些線索上爲什麼會出現使用快速排序時，這樣的急劇增加（ 2.5k和幾乎5倍的元素）。

感謝您的幫助

編輯：代碼用於測試

Record smallRecord[25000]; 
populateArray(smallRecord, 25000); 

int startTime = GetTickCount(); 

for(int times = 0; times < NUMOFTIMES; times++) 
{ 
    populateArray(smallRecord, 25000); 
    myGnomeSort(smallRecord, 25000, compareResult); 
    cout << times << endl; 
} 

int endTime = GetTickCount(); 
float timeMS = ((float) (endTime - startTime))/1000; 

cout << "Time taken: " << timeMS << endl; 

的填入陣列功能只是填充用隨機數數組

Answer 1

其實快速排序擁有的Ø複雜（ N^2），並且它平均是O（N * logN），而不是最壞的情況。因此，不鼓勵使用快速排序，因爲總會存在這樣的數據在其上工作O（N^2）