如何在C++中对vector进行排序_C++ vector排序函数与自定义比较-C++-PHP中文网

如何在C++中对vector进行排序_C++ vector排序函数与自定义比较

尼克

发布： 2025-09-25 18:27:01

原创

628人浏览过

升序排序使用std::sort默认行为，降序需传入std::greater<int>()；自定义排序可使用函数指针或Lambda表达式；std::sort平均和最坏时间复杂度均为O(n log n)，适用于大多数场景，但小数据量、近有序序列或需稳定排序时可考虑插入排序或std::stable_sort。

如何在c++中对vector进行排序_c++ vector排序函数与自定义比较

C++ 中对 vector 排序，通常使用 std::sort 函数，可以自定义比较函数来实现更灵活的排序规则。

使用 std::sort 函数对 vector 进行排序。

如何使用 `std::sort` 函数对 `vector` 进行升序和降序排序？

std::sort 函数是 C++ 标准库 <algorithm> 中提供的排序算法。默认情况下，它使用 < 运算符进行升序排序。

升序排序：

立即学习“C++免费学习笔记（深入）”；

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
  std::vector<int> numbers = {5, 2, 8, 1, 9, 4};

  std::sort(numbers.begin(), numbers.end()); // 默认升序

  std::cout << "升序排序后: ";
  for (int num : numbers) {
    std::cout << num << " ";
  }
  std::cout << std::endl;

  return 0;
}

登录后复制

降序排序：

要进行降序排序，可以使用 std::greater<T> 仿函数作为比较函数。

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
  std::vector<int> numbers = {5, 2, 8, 1, 9, 4};

  std::sort(numbers.begin(), numbers.end(), std::greater<int>()); // 降序

  std::cout << "降序排序后: ";
  for (int num : numbers) {
    std::cout << num << " ";
  }
  std::cout << std::endl;

  return 0;
}

登录后复制

在这个例子中，std::greater<int>() 创建了一个比较函数对象，它定义了 > 运算符的行为，从而实现了降序排序。

如何自定义比较函数对 `vector` 进行排序？

有时，默认的升序或降序排序无法满足需求。例如，需要按照元素的某个特定属性进行排序，或者需要自定义排序规则。这时，可以自定义比较函数。

标书对比王

标书对比王是一款标书查重工具，支持多份投标文件两两相互比对，重复内容高亮标记，可快速定位重复内容原文所在位置，并可导出比对报告。

查看详情

使用函数指针：

#include <iostream>
#include <vector>
#include <algorithm>

struct Person {
  std::string name;
  int age;
};

bool compareByAge(const Person& a, const Person& b) {
  return a.age < b.age; // 按年龄升序
}

int main() {
  std::vector<Person> people = {
    {"Alice", 30},
    {"Bob", 25},
    {"Charlie", 35}
  };

  std::sort(people.begin(), people.end(), compareByAge);

  std::cout << "按年龄排序后: " << std::endl;
  for (const auto& person : people) {
    std::cout << person.name << ": " << person.age << std::endl;
  }

  return 0;
}

登录后复制

使用 Lambda 表达式：

Lambda 表达式提供了一种更简洁的方式来定义比较函数。

#include <iostream>
#include <vector>
#include <algorithm>

struct Person {
  std::string name;
  int age;
};

int main() {
  std::vector<Person> people = {
    {"Alice", 30},
    {"Bob", 25},
    {"Charlie", 35}
  };

  std::sort(people.begin(), people.end(), [](const Person& a, const Person& b) {
    return a.name < b.name; // 按姓名升序
  });

  std::cout << "按姓名排序后: " << std::endl;
  for (const auto& person : people) {
    std::cout << person.name << ": " << person.age << std::endl;
  }

  return 0;
}

登录后复制

Lambda 表达式 [](const Person& a, const Person& b) { return a.name < b.name; } 定义了一个匿名函数，它接受两个 Person 对象作为参数，并返回一个布尔值，指示它们的姓名是否应该交换位置。

性能优化：`std::sort` 的时间复杂度是多少？在哪些情况下应该考虑使用其他排序算法？

std::sort 通常使用 IntroSort 算法，这是一种混合排序算法，结合了快速排序、堆排序和插入排序的优点。平均时间复杂度为 O(n log n)，最坏情况下的时间复杂度也是 O(n log n)。

何时考虑其他排序算法：

数据量非常小： 对于非常小的 vector，插入排序可能更快，因为它具有较低的常数因子。
数据基本有序： 如果 vector 已经接近有序，插入排序或冒泡排序可能更有效。
需要稳定排序： std::sort 不是稳定排序算法，这意味着相等元素的相对顺序可能会改变。如果需要保持相等元素的原始顺序，可以考虑使用 std::stable_sort，但它的性能可能略低于 std::sort。
特定数据类型： 对于某些特定数据类型，例如整数，计数排序或基数排序可能更有效，但这些算法通常需要额外的内存空间。

示例：使用 std::stable_sort：

#include <iostream>
#include <vector>
#include <algorithm>

struct Item {
  int value;
  int index; // 记录原始索引
};

bool compareByValue(const Item& a, const Item& b) {
  return a.value < b.value;
}

int main() {
  std::vector<Item> items = {
    {5, 0},
    {2, 1},
    {5, 2}, // 与第一个 5 值相等
    {1, 3}
  };

  std::stable_sort(items.begin(), items.end(), compareByValue);

  std::cout << "稳定排序后: " << std::endl;
  for (const auto& item : items) {
    std::cout << "Value: " << item.value << ", Index: " << item.index << std::endl;
  }

  return 0;
}

登录后复制

在这个例子中，即使有两个 Item 对象的 value 相同（都为 5），它们在排序后的 vector 中的相对顺序仍然保持不变，即原始索引为 0 的 Item 在原始索引为 2 的 Item 之前。

以上就是如何在C++中对vector进行排序_C++ vector排序函数与自定义比较的详细内容，更多请关注php中文网其它相关文章！