👉基础排序练习

基础算法——排序 II

sort

本章主要展示针对 sort 的使用以及涉及结构体排序的构造办法

关键1：sort 是算法库函数工具，需要头文件 algorithm

关键2：sort 默认对数据从小到大进行排序

关键3：sort 使用格式 sort(开始排序地址，结束排序哨兵)

示意图：

#include <iostream>
#include <algorithm>
using namespace std;

int main () {
    //    下标    0   1  2  3  4  5  6  7  8  9  10
    int a[15] = {999, 3, 2, 4, 9, 8, 0, 7, 6, 5, 1};
	int n = 10; // 根据结果观察，感知排序范围

	sort(a + 0, a + n);
	for (int i = 0; i <= n; i ++) {
		cout << a[i] << ' ';
	}
	cout << endl;
	// 0 2 3 4 5 6 7 8 9 999 1 
    return 0;
}

根据以上结果，发现仅仅对 a[0] ~ a[9] 进行排序。

根据 sort 的运用格式，a + n 表示 a[n] 是哨兵，即 a[10] 是哨兵，不进行排序，因此才有了当前的结果。

请将 sort(a + 0, a + n) 这一行分别改为 sort(a + 0, a + n + 1) 和 sort(a + 1, a + n + 1) 查看结果

练习：若针对一个 a[1] ~ a[100] 的数组，希望将其下标区间 [10, 20] 进行升序排序，则 sort( x, y ); 中 x 和 y 分别应是 ？

{{ select(1) }}

• a+10, a+21
• a+10, a+20
• a+9, a+21
• a+9, a+20

关键4：sort 针对的是排序对象的 < 的判断，若排序对象不存在 < 判断逻辑，则会出错，需要自行构建针对 < 的比较函数。注意，若 sort 具备比较函数，则会优先使用比较函数。

例，利用比较函数，使 sort 对整数从大到小排序。

#include <iostream>
#include <algorithm>
using namespace std;

// 比较函数
bool cmp(int x, int y) {
	return x > y; // 设定 < 判断逻辑
}

int main () {
    //    下标    0   1  2  3  4  5  6  7  8  9  10
    int a[15] = {999, 3, 2, 4, 9, 8, 0, 7, 6, 5, 1};
	int n = 10; 

	sort(a + 0, a + n + 1, cmp); // 带有比价函数的 sort
	for (int i = 0; i <= n; i ++) {
		cout << a[i] << ' ';
	}
	cout << endl;
	// 999 9 8 7 6 5 4 3 2 1 0 
    return 0;
}

例：学生成绩查询

将一行数据构造成结构体数据对象，并对之构建 < 的比较函数

// sort 方式
#include <iostream>
#include <algorithm>
using namespace std;

struct Node { 
    string id, name, score; 
};
const int N = 110;
Node a[N];
bool cmp(Node a, Node b) { 
    return a.id < b.id; // 只关心 < 号的定义。
}

int main() {

    int n; cin >> n;

    for (int i=1; i<=n; i++) {    
        cin >> a[i].id >> a[i].name >> a[i].score;
    }

    sort(a+1, a+1+n, cmp);

    for (int i=1; i<=n; i++) {
        cout << a[i].score << endl;
    }

    return 0;
}

---

TIP

#include <iostream>
#include <algorithm>
 
using namespace std;


struct Node {
	int val;  // 数值   从大到小 
	int id;   // 编号   从小到大 
//	bool operator < (const Node &a) const {
//		return val > a.val || (val == a.val && id < a.id); 
//	}
};

bool cmp(Node x, Node y) {
	return x.val > y.val || (x.val == y.val && x.id < y.id);
}

int main () {
	
	Node a[4] = {
		{},
		{1, 3}, // a[1]
		{1, 2}, // a[2]
		{2, 1}  // a[3]
	};
	int n = 3;
	sort(a + 1, a + n + 1, cmp);
	
	for (int i = 1; i <= n; i ++) {
		cout << a[i].val << " " << a[i].id << endl;
	}


    return 0;
}