使用QuickSort的C ++排序数组结构

2024-05-20 • 问答

我必须使用QuickSort算法对结构数组进行排序（不是内置函数，我必须手动编写），还要测量工作时间并与标准C ++排序函数进行比较。我编译我的代码后，输出文件（sort.txt）看起来相同。我做错了什么？

struct Info
{
    int Birth;
    char Name[20];
    char SurName[25];
};

template <keys T>
struct Comparer {

    bool operator ()(const Info &m1,const Info &m2) const {

        return (T == YEAR ? m1.Birth > m2.Birth : strcmp(m1.Name,m2.Name) > 0);
    }

};

int partition(vector<Info> &vArray,int start,int end) {
    int pivotvalue,pivotIndex,mid;

    mid = (start + end) / 2;
    swap(vArray[start].Birth,vArray[mid].Birth);
    swap(vArray[start].Name,vArray[mid].Name);
    swap(vArray[start].SurName,vArray[mid].SurName);


    pivotIndex = start;
    pivotvalue = vArray[start].Birth;

    for (int scan = start + 1; scan <= end; scan++) {
        if (vArray[scan].Birth < pivotvalue) {
            pivotIndex++;
            swap(vArray[pivotIndex].Birth,vArray[scan].Birth);
            swap(vArray[pivotIndex].Name,vArray[scan].Name);
            swap(vArray[pivotIndex].SurName,vArray[scan].SurName);

        }
    }

    swap(vArray[start].Birth,vArray[pivotIndex].Birth);
    swap(vArray[start].Name,vArray[pivotIndex].Name);
    swap(vArray[start].SurName,vArray[pivotIndex].SurName);
    return pivotIndex;
}

template <keys T>
void quickSort(vector<Info>&vArray,int end) {
    int pivotPoint;
    if (start < end) {

        pivotPoint = partition(vArray,start,end);

        quickSort<T>(vArray,pivotPoint - 1);

        quickSort<T>(vArray,pivotPoint + 1,end);
    }
}

void Print(const vector<Info> Mas)
{
    string path = "sort.txt";
    ofstream Out;
    Out.open(path);
    if (!Out.is_open()) {
        cout << "wdw" << endl;

    }
    else  {
        for (int i = 0; i < (int)Mas.size(); i++)
            Out << Mas[i].Name << " " << Mas[i].SurName << " " << Mas[i].Birth << "\n";
    }
    Out.close();
}

template<keys T>
bool isSorted(vector<Info> Mas)
{
    Comparer<T> c;
    for (int i = 0; i < Mas.size() - 1; i++)
        if (c(Mas[i],Mas[i + 1]))
            return false;
    return true;
}

在主要功能中：

        quickSort<YEAR>(Mas,pow(rows,i));

    Print(Mas);

我的完整代码：https://www.codepile.net/pile/e2z3l7E0

Names.txt和Surnames.txt生成：https://dropmefiles.com/riOmD

这些部分保证不会进行排序：

if (start < end) { 
//... do the sorting
} // else don't

//                   start  end                      
quickSort<YEAR>(Mas,100000,0);

在partition()函数中，您可以添加一些调试打印以使您走上正确的轨道：

    int pivotValue,pivotIndex,mid;

    mid = (start + end) / 2;
    std::cout << "size: " << vArray.size() << " start: " << start << " mid: " << mid
              << " end: " << end << "\n";
    // ...

    for (int scan = start + 1; scan <= end; scan++) {
        std::cout << "scan: " << scan << "\n";
        // ...

您会注意到，您实际上正在超出范围：

size: 1 start: 0 mid: 0 end: 1
scan: 1

vArray[1]在vArray.size()为1时是非法的，因此该程序具有未定义的行为。

您的Info有一个char Name[10]成员，这意味着最多只能存储9个字符的名称。您的names.txt文件包含59个更长的名称。因此，您将超出范围，可能会写入以下SurName成员中。

使用QuickSort的C ++排序数组结构

lijunjiji 回答：使用QuickSort的C ++排序数组结构

大家都在问