c++ - 冒泡排序 vector

Question

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

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() 是对对象进行排序的属性。

Answer 1

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

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.
            }
        }
    }
}

你看到外环了吗？它有两个用途。第一，它实际上确保我们在仍然有元素乱序的情况下梳理 vector (我相信在算法教科书中称为 inversions)，第二，它让我们不会毫无意义地检查由于之前的内循环迭代而“冒泡”到 vector 末尾的元素。

但是冒泡排序不是一个好的算法(除非你确定你的输入数据几乎已经排序，在这种情况下冒泡排序会非常有效。)相反，你可以这样做:

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

差不多就是这些了。<​​/p>

一些注意事项:

• 您必须包括 <algorithm> .
• 函数的第三个参数叫做“lambda”。 Lambda 基本上是没有名称的函数，您可以将它们写在代码中间并传递。我建议您仔细阅读它们，因为它们是计算和编程中的一个重要概念(与您使用的语言无关。)
• 因为您希望项目按相关性和 std::sort 降序排列默认情况下按升序(？)排序，lambda 在 b 时返回 true的相关性小于 a的。
• 使用标准排序算法，除了比您的手写代码更短、更甜美，而且更可能是正确的之外，还意味着您通常可以获得非常好的性能(包括算法 Big-O 性能和实现-明智的。)冒泡排序肯定会好得多(在一般情况下。)