1

我正在尝试根据其中一个对象属性对对象向量进行排序。每个对象都有一个与之关联的整数值。我正在尝试使用冒泡排序按降序对数组进行排序，但它似乎没有做任何事情。这是我尝试过的：

void Database::sort (vector<Play*> &vec) {
  for (int i = 0; i < (vec.size() - 1); i++) {
    if (vec.at(i)->getRelevance() < vec.at((i + 1))->getRelevance()) {
      Play *tempObj = new Play(vec.at(i));
      vec.at(i) = vec.at((i +1));
      vec.at((i + 1)) = tempObj;
    }
  }
}

getRelevance() 是用于对对象进行排序的属性。

4

1 回答 1

4

您的代码的问题之一是它只包含一个循环！如果要进行冒泡排序，则需要两个嵌套循环。例如，这可能会起作用：

void Database::sort (vector<Play*> &vec) {
    bool have_swapped = true;
    for (unsigned j = 1; have_swapped && j < vec.size(); ++j) {
        have_swapped = false;
        for (unsigned i = 0; i < vec.size() - j; ++i) {
            if (vec[i]->getRelevance() < vec[i + 1]->getRelevance()) {
                have_swapped = true;
                Play * tempObj = vec[i];  // Just use:
                vec[i] = vec[i + 1];      //    std::swap(vec[i], vec[i + 1]);
                vec[i + 1] = tempObj;     // instead of these three lines.
            }
        }
    }
}

看到外环了吗？它有两个用途。第一，它实际上确保我们在仍然存在乱序元素的情况下梳理向量（我相信在算法教科书中称为反转），第二，它让我们不会遍历并毫无意义地检查“冒泡的元素” " 由于先前的内部循环迭代，一直到向量的末尾。

但是冒泡排序不是一个好的算法（除非您确定您的输入数据几乎已排序，在这种情况下冒泡排序可能非常有效。）相反，您可以执行以下操作：

std::sort (vec.begin(), vec.end(),
    [](Play * a, Play * b){return b->getRelevance() < a->getRelevance();}
);

差不多就是这样。

一些注意事项：

  • 你必须包括<algorithm>.
  • 作为函数的第三个参数的那个东西被称为“ lambda ”。Lambda 基本上是没有名称的函数，您可以在代码中间编写并传递。我建议您阅读它们，因为它们是计算和编程中的一个重要概念（与您使用的语言无关。）
  • 由于您希望项目按相关性降序排序并std::sort默认升序排序（？），因此当b' 的相关性小于a' 时，lambda 返回 true。
  • 使用标准排序算法，除了比你的手工代码更短更甜，而且更可能是正确的，这意味着你通常可以获得非常好的性能（算法 Big-O 性能和实现方面）。冒泡排序肯定会好得多（在一般情况下）。
于 2013-09-16T23:25:38.900 回答