C/C++ 基本算法——排序

type

status

date

slug

summary

C++的sort( )排序

STL的排序函数sort()有以下两种定义：

返回值：无

复杂度：

提示：它排序的范围是[first, last)，包括first，不包括last 其中 first 是要排序的第一个元素的迭代器，而 last 则是最后一个元素之后的迭代器。这表示排序包括了 first 所指向的元素，但不包括 last 所指向的元素。

sort( )自带4中排序：less、greater、less_equal、greater_equal。

默认情况下，sort( )按从小到大进行排序，less可以不写。

结合cmp( )函数，sort( )函数可以对结构体进行排序，例：

C++的sort( )有两个优点：能在原数组上排序，不需要新的空间；能在数组的局部区间上排序。

【题目描述】有n个自然数，不相同的数不超过10000个。现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。

【输入描述】第一行输入整数n，表示自然数的个数。第2~第n+1行每行输入一个自然数。其中，每个数均不大于。

【输出描述】输出m行（m为n个自然数中不相同数的个数），按照自然数从小到大的顺序输出。每行输出两个整数，分别为自然数和该数出现的次数，其间用一个空格隔开。

【输入样例】 8 2 4 2 4 5 100 2 100

【输出样例】 2 3 4 2 5 1 100 2

【题目描述】每张票据有唯一的ID号，且所有ID号为连续的，但ID号开始的数码是随机的。因为工作人员输入错误，造成某个ID断号，另外一个ID重号。编写程序，找出断号的ID与重号的ID。假设断号不可能发生在最大和最小号。

【输入描述】输入整数N（N<100）表示后面要读入的行数。接着读入N行数据，每行数据长度不等，是用空格分开的若干个（不大于100）正整数（不大于）。

【输出描述】要求程序输出一行数据，包括两个整数m、n，用空格分隔。其中，m表示断号ID，n表示重号ID。

【输入样例】 2 5 6 8 11 9 10 12 9

【输出样例】 7 9

💡

这道题麻烦的是数据的输入，比起数组，作为容器的vector要更加灵活。避开需要计算数组中数据的长度，通过输入的行数来进行扫描更加方便。

【题目描述】期末考试结束后，每个学生有3门成绩：语文，数学，英语。先按总分从高到低排序；如果总分相同，就按语文成绩从高到低排序；如果语文成绩相同，则让学号小的学生排在前面。任务：按上述规则排序后，输出前5名学生的学号与总分。

【输入描述】第一行输入一个正整数n（），表示学生人数。第2到第n+1行，每行输入3个用空格隔开的数字，每个数字都在0到100之间。第j行的3个数字依次表示学号为j-1的学生的语文，数学，英语成绩。学号按输入顺序决定。

【输出描述】输出共有5行，每行是两个用空格隔开的正整数，依次表示学生的学号和总分。

【输入样例】 6 80 75 90 85 90 88 92 88 89 75 92 86 85 80 82 89 82 78

【输出样例】 3 269 2 263 4 253 6 249 5 247