STL中排序函数的用法（Qsort，Sort，Stable_sort，Partial_sort，List::sort）

阅读量：4553 次

发布时间：2019-06-08

本文共 3063 字，大约阅读时间需要 10 分钟。

都知道排序很重要，也学了各式各样的排序算法，冒泡、插入、归并等等，但其实在ACM比赛中，只要不是太慢的算法，都可以适用（除非某些题目卡时间卡的很死），这个时候，速度与技巧便成了关键，而在C++的标准库中，就已经定义好了一些排序函数，下面来一一介绍它们吧=7=

Qsort

函数原型为void qsort(void*base,size_t num,size_t width,int(__cdecl*compare)(const void*,const void*));包含四个参数，分别是待排序数组首地址、数组中待排序元素数量、各元素的占用空间大小、指向函数的指针（就是自己的排序函数），这个函数在C语言中就可以使用了，可以不包含第四个参数进行对数组的排序，此时系统会自动按照从小到大的排序，例如：

int a[] = {
   4,1,2,3,5,7,6};qsort(a,7,sizeof(a[0]));//结果：1 2 3 4 5 6 7

好，那么qsort如何对结构体进行排序呢，我们知道，对结构体数组的排序需要自己写一个排序函数，但是和其他函数不一样的是，qsort的排序函数有其固定的形式，例如：

struct node{    int id,num;}a[6] = {
   {
   1,3},{
   2,4},{
   3,1},{
   4,2},{
   5,6},{
   6,5}};int cmp(const void *a,const void *b){    node *aa = (node *)a;    node *bb = (node *)b;    if(aa->num == bb->num){        return aa->id < bb->id;    }    return aa->num > bb->num;    //按num值升序排序}qsort(a,6,sizeof(a[0]),cmp);

可以看到，cmp函数形参不能直接定义为相应类型，只能定义为const void *p 类型，然后强制转换为相应类型再做出处理。真是因为如此，我们在ACM中不会太经常也不建议用qsort函数，但还是得明白一下操作。

Sort

这个函数相信大家都很熟悉了，就是常用排序函数，给给定区间内进行排序，时间复杂度为O(N*logN),参数有三个，分别是首地址、末地址和排序函数，第三个参数省略时按照从小到大排序，例如:

1 int a[] = {
   4,1,2,3,5,6};2 sort(a,a+6);3 4 //排序结果: 1 2 3 4 5 6

稍微难一点的就是对结构体数组进行排序，此时，sort函数就有多种选择方式了，可以在结构体内重载操作符，写比较函数或者仿函数等都可以，例如：

1 struct node{ 2     int id,num; 3  4     //重载比较符 5     bool operator < (const node &b) const{ 6         if(num == b.num){ 7             return id < b.id; 8         } 9         return num > b.num;10     }11 }a[6] = {
   {
   1,3},{
   2,4},{
   3,1},{
   4,2},{
   5,6},{
   6,5}};12 13 14 //编写比较函数15 int cmp(node &a,node &b){16     if(a.num == b.num){17         return a.id < b.id;18     }19     return a.num > b.num;20 }21 22 sort(a,a+6);    //重载比较符23 sort(a,a+6,cmp);    //编写比较函数

不使用结构体，使用仿函数就是:

1 //编写仿函数 2 class CMP{ 3     public: 4         CMP(int _id,int _num):id(_id),num(_num){} 5         int id; 6         int num; 7         bool operator < (const node &b) const{ 8             if(num == b.num){ 9                 return id < b.id;10             }11             return num > b.num;12         }13 };14 15 vector
     
      a;16 sort(a,a+6);

基本上Sort的操作就是这些了。

Stable_sort

其实你会发现不仅仅sort有stable_sort，partition也有stable_partition，我们都知道sort是一个不稳定的排序，但stable_sort就是如字面意思一样，是一个稳定的sort排序，那么你可能有疑问，排序后，相同的元素会在一起，稳定不稳定不都是一样的么，如果你存在这个疑问的话，那就肯定还是做题力度不够=7=，你只想到了对元素表面的排序，如果是对元素的某种性质排序呢，例如：

1 string s[4] = {
   "spring","lip","eye","winter"};2 3 bool cmp(string a, string b){4     return a.size() < b.size();5 }6 7 sort(s,s+4,cmp);

对于这段代码，"lip"和"eye"对于比较函数来说是相等的，所以排序后结果可能lip在eye的前面也可能在eye后面，但是如果这里使用stable_sort，排序前lip在eye前面，不管排序次数如何，lip一定会排在eye的前面。

其他用法和sort一样。

Partial_sort

和字面意思一样，部分排序，函数有三个参数，分别是区间要排序的首位置、要排序的末位置以及区间末位置，函数的作用就是把区间内前n个元素排序，其他元素则依次排在末尾，例如：

int a[] = {
   6,5,4,3,2,1};partial_sort(a,a+3,a+6);//排序结果: 1 2 3 6 5 4

函数其他用法和sort相同，也就没什么好讲的=7=

List::sort

这个是list容器中专有的排序函数，直接对迭代器操作，使用方式为：

1 list
     
      a;2 a.sort();

那么全部的排序函数已经讲完了，如果在之前你只知道一个sort或者qsort的话，是不是突然觉得知道了很多新东西呢，其实STL的东西远不止这些，学好了STL，对于我们做题真的是有质和速度的双从提升。

还有就是文中提及的仿函数，这个东西也是STL里面的一大类，会专门将这个的，嘻嘻。

后记：有人和我说nth_element函数的讲解，但是nth_element并不算是排序函数，所以没有写在这里，都会写的=7=

转载于:https://www.cnblogs.com/xenny/p/9404758.html

你可能感兴趣的文章