troysps 2020-01-24
c++
算法库里有一个强大的排序函数sort
,使用方便,速度快,基本上能解决我们在平时遇到的大多数排序问题,使用 sort
函数需要包含算法库:#include <algorithm>
sort
排序定义原型:
void sort (RandomAccessIterator first, RandomAccessIterator last);
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
[first,last)
区间的元素默认按升序,如有比较函数,按比较函数规则排序sort
不是稳定排序(相同的元素在排序后相对位置会发生变化)sort(begin, end, cmp)
begin :为指向待待排序数组的第一个元素的指针
end :为指向待排序数组的最后一个元素的下一个位置的指针
cmp :参数为排序的准则,默认以非降序排序
举例说明:
#include <algorithm>//算法库 int main() { int a[5] = {1, 3, 4, 2, 5}; std::sort(a+0, a + 5); for (int i = 0; i < 5; i++) printf("%d ",a[i]); return 0; }
自定义cmp参数,降序排序
#include <cstdio> #include <algorithm>//算法库 bool cmp(int x, int y) { return x > y;//这样是降序排序,改成return x<y;呢? } int main() { int a[5] = {1, 3, 4, 2, 5}; sort(a+0, a + 5, cmp); for (int i = 0; i < 5; i++) printf("%d ",a[i]); return 0; }
对基本数据类型的数组进行排序,我们也可以使用标准库函数进行排序,例如,上述排序的代码可以修改为:
sort(a, a + 5, less<int>());
stable_sort
排序void stable_sort ( RandomAccessIterator first, RandomAccessIterator last );
void stable_sort ( RandomAccessIterator first, RandomAccessIterator last,Compare comp );
[first,last)
区间的元素默认按升序,如有比较函数,按比较函数规则排序stable_sort
是稳定排序(相同的元素在排序后相对位置不变)partial_sort
排序void partial_sort (RandomAccessIterator first, RandomAccessIterator middle,RandomAccessIterator last);
void partial_sort (RandomAccessIterator first, RandomAccessIterator middle,RandomAccessIterator last, Compare comp);
[first, middle)
含有范围[first, last)
中已排序的 middle - first
个最小元素。[middle, last)
中剩余的元素顺序未指定。operator<
比较元素。否则用给定的二元比较函数
comp 比较元素。[first, middle)
的元素执行make_heap()
操作构造一个最大堆[middle, last)
中的每个元素和first
进行比较,first
内的元素为堆内的最大值[first, middle)
内的元素进行调整,使其保持最大堆序[first, middle)
内的元素做一次对排序sort_heap()
操作,使其按增序排列。(last-first)log(middle-first)
次应用 cmp
。sort
函数内部排序是用小于号进行比较的,所以我们只需对该类型结构体的小于号进行重载即可
对于结构体排序,还可以用重载结构体或类的比较运算符的方法,上述代码可以修改为:
struct Stu{ int yw; int sx; bool operator <(const Stu& A) const { if (yw == A.yw) return sx > A.sx; else return yw < A.yw; } }; Stu a[1000]; sort(a+0,a+100);//对数组下标从0~99之间元素按照cmp排序规则排序
例题:noi.openjudge.cn 1.9 04:谁拿了最多奖学金
如果要想让v2也进行排序,需要把k2和v2组装成新的类,作为k2,才能参与比较。// 1.1 告诉干活的人 输入流位置 读取hdfs中的文件。每一行解析成一个<k,v>。每一个键值对调用一次map函数