1

我正在编写一个快速排序，当被排序的数组的长度很小时，它会切换到插入排序。我已经运行了一些测试，据我所见，当被排序的数组是 200 个元素或更少时，切换到插入排序会更快。这看起来真的很大，我期待接近 20。200 是合理的还是我的实现方式之一？我使用了基本的维基百科算法。

void quicksort(int list[asize], int left, int right)
{
    int pivotindex;
    int newpivotindex;

    if (left < right)
    {
            if ((right-left)<=200)
            {
            insertionsort(list,left,right);
            }
    }
    else
    {
        pivotindex = r_rand(left,right);
        newpivotindex = partition(list, left, right, pivotindex);

        quicksort(list, left, newpivotindex-1);
        quicksort(list, newpivotindex+1, right); 
    }
    return;
}

int partition(int* list,int left, int right, int pivotindex)
{
int pivotvalue = list[pivotindex];
int temp;
int i;
int storeindex;

temp=list[pivotindex];
list[pivotindex]=list[right];
list[right]=temp;

storeindex=left;

for (i=left;i<right;i++)
{
    if (list[i] < pivotvalue)
    {
        temp=list[i];
        list[i]=list[storeindex];
        list[storeindex]=temp;

        storeindex++;
    }
}

temp=list[storeindex];
list[storeindex]=list[right];
list[right]=temp;

return storeindex;
}

void insertionsort(int* list, int left, int right)
{
int i;
int item;
int ihole;

for (i=left;i<=right;i++)
{
    item=list[i];
    ihole=i;
    while (ihole > 0 && list[ihole-1] > item)
    {
        list[ihole]=list[ihole-1];
        ihole--;
    }
    list[ihole]=item;
}

return;
}
4

0 回答 0