-1

嗨，我正在测试几种排序算法在对 2500 到 25000 大小之间的数组进行排序时的性能。我比较的两种排序是 Gnome 排序和快速排序，从我所读到的这些快速排序应该是快得多，但 Gnome 排序在每种情况下都击败了它。

快速排序的代码是：

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;

填充数组函数只是用随机数填充数组

4

1 回答 1

-1

实际上，快速排序的复杂度为O(N^2)，平均为O(N * logN)，而不是在最坏的情况下。所以不鼓励使用快速排序，因为总会存在这样的数据，它可以工作O(N^2)

于 2013-03-24T20:33:37.237 回答