C++数组如何排序 标准库sort函数的使用示例

最方便的c++++数组排序方法是使用标准库的std::sort函数。1. 对基本数据类型数组排序时，包含头文件后，直接调用std::sort(arr, arr + n)即可完成升序排序；2. 若要自定义排序规则，可通过传入比较函数或lambda表达式实现，例如降序排序可使用std::sort(arr, arr + n, [](int a, int b) { return a > b; })；3. 对结构体数组排序时，需定义比较函数并访问结构体成员，如按年龄排序应定义bool compareperson(const person& a, const person& b) { return a.age

C++数组排序，最方便的就是用标准库的sort函数。它效率高，用法灵活，能满足大多数排序需求。

直接用std::sort就完事了。

使用std::sort排序基本数据类型数组

std::sort函数位于头文件中，所以首先要包含这个头文件。它接受两个迭代器作为参数，表示要排序的范围。对于数组来说，可以使用数组的首地址和尾地址。

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

#include 
#include 

int main() {
  int arr[] = {5, 2, 8, 1, 9, 4};
  int n = sizeof(arr) / sizeof(arr[0]); // 计算数组长度

  std::sort(arr, arr + n); // 从arr[0]到arr[n-1]排序

  std::cout << "排序后的数组：";
  for (int i = 0; i < n; ++i) {
    std::cout << arr[i] << " ";
  }
  std::cout << std::endl;

  return 0;
}

这段代码展示了如何对一个整数数组进行升序排序。arr是数组名，arr + n指向数组最后一个元素的下一个位置。

使用std::sort自定义排序规则

std::sort还可以接受一个可选的第三个参数，用于指定排序的比较函数。这个比较函数应该接受两个参数（要比较的元素），并返回一个布尔值，指示第一个参数是否应该排在第二个参数之前。

例如，要对数组进行降序排序，可以这样写：

#include 
#include 

bool compare(int a, int b) {
  return a > b; // 降序排列
}

int main() {
  int arr[] = {5, 2, 8, 1, 9, 4};
  int n = sizeof(arr) / sizeof(arr[0]);

  std::sort(arr, arr + n, compare); // 使用自定义比较函数

  std::cout << "降序排序后的数组：";
  for (int i = 0; i < n; ++i) {
    std::cout << arr[i] << " ";
  }
  std::cout << std::endl;

  return 0;
}

这里，compare函数定义了降序的规则。如果a大于b，则返回true，表示a应该排在b前面。

使用lambda表达式简化比较函数

在C++11及以后的版本中，可以使用lambda表达式来简化比较函数的定义。例如，上面的降序排序可以这样写：

#include 
#include 

int main() {
  int arr[] = {5, 2, 8, 1, 9, 4};
  int n = sizeof(arr) / sizeof(arr[0]);

  std::sort(arr, arr + n, [](int a, int b) { return a > b; }); // 使用lambda表达式

  std::cout << "降序排序后的数组：";
  for (int i = 0; i < n; ++i) {
    std::cout << arr[i] << " ";
  }
  std::cout << std::endl;

  return 0;
}

lambda表达式 [](int a, int b) { return a > b; } 相当于一个匿名函数，直接在std::sort函数中定义了比较规则，代码更加简洁。

如何对结构体数组进行排序

如果需要对结构体数组进行排序，比较函数需要能够访问结构体的成员。

#include 
#include 

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

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

int main() {
  Person people[] = {{"Alice", 30}, {"Bob", 25}, {"Charlie", 35}};
  int n = sizeof(people) / sizeof(people[0]);

  std::sort(people, people + n, comparePerson);

  std::cout << "按年龄排序后的数组：\n";
  for (int i = 0; i < n; ++i) {
    std::cout << people[i].name << ": " << people[i].age << std::endl;
  }

  return 0;
}

这里，comparePerson函数比较两个Person对象的age成员，从而实现按年龄排序。

std::sort的性能考量

std::sort通常使用一种称为 IntroSort 的排序算法，它是快速排序、堆排序和插入排序的混合体。这种算法在大多数情况下都能提供良好的性能，平均时间复杂度为 O(n log n)。在最坏情况下，IntroSort 会切换到堆排序，从而保证时间复杂度不会退化到 O(n^2)。

但是，对于小规模数组，插入排序可能更快。std::sort的实现通常会对小规模数据采用插入排序。

除了std::sort还有哪些排序方法？

除了std::sort，C++标准库还提供了其他排序相关的函数，例如std::stable_sort和std::partial_sort。

• std::stable_sort：稳定排序，即相等元素的相对顺序在排序后保持不变。这在某些场景下非常重要。
• std::partial_sort：部分排序，只对数组的一部分进行排序。例如，找到数组中最小的k个元素。

如果对性能有极致要求，可以考虑手动实现排序算法，例如快速排序、归并排序等。但通常情况下，std::sort已经足够优秀。

如何避免排序过程中的内存拷贝

对于大型对象数组，排序过程中可能会涉及大量的内存拷贝，这会影响性能。一种优化方法是指针排序。

#include 
#include 
#include 

struct Data {
  int id;
  std::string value;
};

bool compareData(const Data* a, const Data* b) {
  return a->id < b->id;
}

int main() {
  std::vector data = {{3, "value3"}, {1, "value1"}, {2, "value2"}};
  std::vector dataPtrs;
  for (auto& d : data) {
    dataPtrs.push_back(&d);
  }

  std::sort(dataPtrs.begin(), dataPtrs.end(), compareData);

  std::cout << "排序后的数据：\n";
  for (auto ptr : dataPtrs) {
    std::cout << ptr->id << ": " << ptr->value << std::endl;
  }

  return 0;
}

在这个例子中，我们创建了一个指向Data对象的指针数组，然后对指针数组进行排序。这样可以避免在排序过程中拷贝Data对象，提高性能。