sort函数（快速排列）的使用方法

今天我们了解一下sort的使用方法。

一般的排序方法，如冒泡排序法，它的时间复杂度为n^2，这种方法的效率低下，代码相对较长，容易误事。

而快速排列（简称快排），它的时间复杂度仅为n*log2(n)，代码也相对简短，只需一个函数。

sort函数包含在头文件为#include<algorithm>的c++标准库中，调用标准库里的排序方法可以不必知道其内部是如何实现的，只要出现我们想要的结果即可！

快排之所以快，因为它使用了分治算法，同冒泡排序一样，快排也属于交换排序。

一个视频看懂快速排序原理

秒懂算法快速排序-动画4分钟精讲

格式

一维数组正序快排：

sort（数组名，数组名+长度）；

一维数组倒序快排：

sort（数组名，数组名+长度，greater<数组类型>（））；

结构体数组排序：

1.按单个成员排序

sort（结构体名，结构体名+长度，cmp）；
bool cmp（结构体类型名（空格）a，结构体类型名（空格）b）
{
    //自定义排序方式
    /*
    正序排列：return a.元素<b.元素；
    倒序排列：return a.元素>b.元素；
    */
}

2.按多个成员排序

sort（结构体名，结构体名+长度，cmp）；
bool cmp（结构体类型名（空格）a，结构体类型名（空格）b）
{
    if(优先级条件)
    //自定义排序方式
    if（第二优先）
    //自定义排序方式
    if（第三优先）
    //自定义排序方式
        …………
    
    
    
    
    /*
    正序排列：return a.元素<b.元素；
    倒序排列：return a.元素>b.元素；
    */
}

可能不是特别懂，看个例子就明白了

设：有结构体a

struct node
{
    int x,y,z;
}a[100]

现在要用快排按x的降序排列，x相同就按y的降序排列，y相同就按z的升序排列，代码如下

sort(a，a+strlen(a),cmp);
bool cmp(node a,node b)
{
    if(a.x<b.x)
    return a.x>b.x;
    if(a.y<b.y)
    return a.y>b.y;
    return a.z<b.z;
}

题目应用

NOI / 4.6算法之贪心：2407:书架（详解）_mooczhimahu的博客-CSDN博客