0

我必须跟踪此选择排序中的所有比较，但是当我这样做时，仅返回 1 作为 1000 列表中的值。我不确定我是否正确实现了它，但我确定我正确放置了比较计数/ . 通常，选择排序具有固定数量的关键比较，但我们的讲师禁止使用公式来跟踪它们。我很好奇为什么这个输出不断返回：

comp = 1
swap = 1 

template <class elemType>
void selectionSort(elemType list[], int length)
{
    int loc, minIndex;
    int first; 
    int last, second;
    int swaps =0;
    int comp = 0;

    minIndex = first;
    for (loc = 0; loc < length; loc++)
    {
        comp+=1; 

        for(loc = first +1; loc<=last; loc++)
        {
            comp+=1;
            if(list[loc]<list[minIndex])
                minIndex=loc;
            comp+=1;
        }
        elemType temp;
        temp= list[first];
        list[first]= list[second];
        list[second] = temp;


        swaps+=1;
    }

    //  comp = (length *(length-1)/2);

    cout<<"swaps= "<<swaps<<endl;
    cout<<"comps= "<<comp<< endl;
}

任何想法表示赞赏

4

1 回答 1

1

我猜你的排序本身不起作用。您需要正确初始化last,first和second变量（特别是last），然后移动（增量）它们。

由于您的last变量默认为0loc<=last，因此由于第二个 for 循环中的条件如您所愿，它不会执行迭代。我认为您需要将其初始化为：

 last = length-1;

还有一个问题：在两个循环中，您都使用相同的索引变量，即loc。我认为您需要使用两个不同的变量。

for (loc = 0; loc < length; loc++)
{
  comp+=1; 
   for(loc = first +1; loc<=last; loc++)
   {

一旦您修复了逻辑以使其执行完整排序，您将获得正确的计数。

于 2012-11-02T19:08:45.313 回答