sort排序

一、sort函数

sort 是一个c++已经为我们实现好的工具，当我们要用它时，需要先引入一个算法的库"algorithm"。

sort 可以排序任何类型的元素，包括我们自己定义的结构体。

sort(arr + i, arr + j);

默认从小到大，被排序的是arr[i]到arr[j-1]

#include "iostream"
#include "algorithm"
using namespace std;
int main() {
    int arr[5] = {5, 3, 1, 2, 4};
    sort(arr, arr + 5);     // 1 2 3 4 5
    return 0;
}

二、结构体

1、结构体的构造方法

struct Student {
    int num;
    int score;
	
    // 默认构造函数
    // 不能出现两个默认构造函数
    Student() {
        num = 0;
        score = 0;
    }
	
    // 带参构造函数
    Student(int num, int score) {
        this->num = num;
        this->score = score;
    }
};

2、初始化列表

struct Node {
    int num;
    string name;
    Node(){};
    // 初始化列表
    Node(int n, string s):num(n),name(s){};
};

1. 函数的参数列表不能省略
2. 必须写大括号

3、构造方法的使用

/**
 * 结构体构造函数
 * @author  王铭颢
 * @Date  2022/11/22 17:14
 */

#include "iostream"
using namespace std;
struct Student {
    int num;
    int score;
    Student() {
        num = 0;
        score = 0;
    }

    Student(int num, int score) {
        this->num = num;
        this->score = score;
    }
};

int main() {
    int num, score;
    cin >> num >> score;
    Student s = Student(num, score);
    cout << s.num << " " << s.score << endl;
    return 0;
}

三、sort"第三参"：排序方法

1、从大到小排序

greater 表示“更大”，<int>表示待排序的数组中的元素类型为 int

/**
 * Sort基本使用
 * @author  王铭颢
 * @Date  2022/11/22 14:52
 */

#include "iostream"
#include "algorithm"

using namespace std;

int main() {
    int arr[5] = {5, 3, 1, 2, 4};
    cout << endl;
    sort(arr, arr + 5, greater<>());     // 5 4 3 2 1
    return 0;
}

2、cmp()函数

cmp通过回调函数（函数的指针）的方式，作为第三参传入给sort

sort通过cmp函数的返回值进行排序

cmp函数参数与返回值

1. x：前一个值
2. y：后一个值
3. 返回值：return x > y => 结果 5 4 3 2 1

/**
 * sort第三参：cmp
 * @author  王铭颢
 * @Date  2022/11/22 16:46
 */


#include "iostream"
#include "algorithm"

using namespace std;

bool cmp(int x, int y) {
    return x > y;
}

int main() {
    int arr[5] = {5, 3, 1, 2, 4};
    sort(arr, arr + 5, cmp);    // 5 4 3 2 1 
    for (int i: arr) {
        cout << i << " ";
    }
    return 0;
}

3、结构体排序

bool cmp(Student s1, Student s2) {
    return s1.score > s2.score;
}

4、浮点数排序

bool cmp(double a, double b) {
    if(fabs(a-b) < EPSILON) return true;
    else return a < b;
}

四、代码

1、对3取余排序

我们有N 个正整数，均小于 10000。现在需要将这些正整数按照除以2的余数从小到大排序，即除以3余0的数排在除以3余1的数前面，除以3余1的数排在除以3余2的数前面。如果余数相等，则按照正整数的值从小到大排序。

/**
 * 对三取余的排序
 * @author  王铭颢
 * @Date  2022/11/22 17:04
 */

/*
 * 我们有N 个正整数，均小于 10000。
 * 现在需要将这些正整数按照除以3的余数从小到大排序，
 * 即除以3余0的数排在除以3余1的数前面，除以3余1的数排在除以3余2的数前面。
 * 如果余数相等，则按照正整数的值从小到大排序。
 */

#include "iostream"
#include "algorithm"

using namespace std;

bool cmp(int x, int y) {
    if (x % 3 == y % 3) return x < y;
    else return x % 3 < y % 3;
}

int main() {
    int arr[9] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    sort(arr, arr + 9, cmp);
    for (int i: arr) {
        cout << i << " ";
    }
    return 0;
}

2、结构体排序

/**
 * 结构体的排序
 * @author  王铭颢
 * @Date  2022/11/22 17:41
 */

#include "iostream"
#include "algorithm"

using namespace std;

struct Student {
    string name;
    int score;

    Student() {};

    Student(string name, int score) {
        this->name = name;
        this->score = score;
    }
};

bool cmp(Student s1, Student s2) {
    return s1.score > s2.score;
}

Student s[3];

int main() {
    for (int i = 0; i < 3; ++i) {
        cin >> s[i].name >> s[i].score;
    }
    sort(s, s + 3, cmp);
    for (int i = 0; i < 3; ++i) {
        cout << s[i].name << " " << s[i].score << endl;
    }
    return 0;
}

3、浮点数排序

/**
 * 浮点数字的排序
 * @author  王铭颢
 * @Date  2022/11/22 17:50
 */

#include "iostream"
#include "algorithm"
#include "cmath"

using namespace std;
double arr[5];
const double EPSILON = 1e-6;

bool cmp(double a, double b) {
    if(fabs(a-b) < EPSILON){
        return true;
    }else {
        return a < b;
    }
}

int main() {
    for (int i = 0; i < 5; ++i) {
        cin >> arr[i];
    }
    sort(arr, arr + 5, cmp);
    for (int i = 0; i < 5; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}