c++ - 使用指针对用户定义对象的 C++ 数组进行排序？

Question

这是我的第一个问题，所以请不仅就问题给我反馈，还要给我提出问题的反馈(谢谢)。

在我上一次 CS 201 的作业中，我们设计了一个代表航空公司航类的类，它包含一些私有(private)数据:

string airline, originAirport, destinationAirport;
int flightNumber, departureTime, arrivalTime; //times from 0000 to 2359

部分任务是显示单个机场的所有出发或到达(由用户选择)。为了获得额外的分数，输出将按升序排序(最早的时间在前)。讲师没有教我们如何使用 std::sort from 因此(我假设)的想法是设计我们自己的排序方法。

我的想法是根据排序的结果填充一个Flight指针数组；但是我遇到了一个问题。这是我进行排序的代码:

for(i=0; i<maxArraySize; i++)
{
    minIndex = i; //assume that element i is the earliest arrival time
    for(j=0; j<maxArraySize; j++) // j=i produced unsorted results
    {
        if (flightArray[j].getArrivalTime() < flightArray[minIndex].getArrivalTime())
            minIndex = j;
    } // at the end of this loop, I now have the smallest flight time's index
    pointerArray[i] = &flightArray[minIndex];
} //when the loop terminates I *should* have a sorted list of pointers (but I don't)

我查看了输出以查看问题出在哪里，然后我意识到所有指针都指向同一个航类(确实有最早的到达时间)。这让我相信问题在于我的代码没有排除已经放入 pointerArray 的航类。

除了“消隐”我刚刚指向的航类(这违背了指针的目的)之外，我找不到任何方法来“忽略”已经有指针指向它们的航类。

我怎样才能解决这个问题？

我想澄清一下，我已经以非常 hack-y 的方式解决了这个问题。我对这个解决方案不满意，因为我觉得它不是最优的，但它确实有效。我并不想让 SO 完成我的任务，只是帮助我成为一个更好的程序员

Answer 1

基本上，您需要对数组进行排序。有很多很多排序算法，您将在数据结构和算法类(class)中学习重要的算法。最佳排序算法是 O(n lg n)(参见维基百科中的快速排序和归并排序。std::sort 也是 O(n lg n) 时间复杂度。

冒泡排序和插入排序是两种非常容易实现的简单排序算法。第二种在实践中更有效(即使两者都是 O(n2))。

关于你的问题风格，这是一个写得很好的第一个问题。

PS:如果您不知道 O(n) 是什么意思，请查看 this .

编辑至于为什么当前的方法不起作用，观察内循环总是找到整个数组的最小值，因此它总是返回相同的结果。

如果您想尽可能少地更改您的代码，这里有一个想法，前提是到达时间都是不同的(即，不是两个到达时间相同的航类。这可能是单一机场的固有含义 在赋值中):只存储之前找到的最小到达时间，如果第 j 个项目的到达时间不等于存储的最小值，则只将 j 分配给 minIdex。除了变量定义之外，它只会在您的代码中添加一行。我将实现保存为练习。

另一种方法，对于具有非不同值的数组，它从数组中删除找到的最小值，或将其值设置为最大值。这虽然改变了数组的内容，因此您需要先复制它。