C++（STL排序函数）

学习目标

1. STL排序函数
2. STL去重函数

计算机语言发展历史(三)

第三代计算机语言是高级语言。用高级语言编写的程序易学、易读、易修改,通用性好,不
依赖于机器。高级语言的发展分为两个阶段,以1980年为
分界线,前一阶段属于结构化语言或者称为面向过程的语言,后一阶段属于面向对象的语言。
例如C语言就是结构化的语言,而C++就是面向对象的语言。

排序函数Sort

STL算法库和算法

●C++STL(标准模板库)是一套功能强大的库,它提供了丰富的数据结
构和算法支持。
● 其中algorithm(算法)库包含很多常用的算法,比如排序。
● 熟练掌握STL算法的使用,可以让我们在编程过程中事半功倍。
● STL算法一般以函数的方式提供

STL排序算法(函数)

在C++的STL中,提供了用于排序的函数sort,直接调用即可
● 一般使用方法:

#include<algorithm>//必须包含的头文件sort(a+start,a+end+1);//进行排序

● 功能:对数组a从a[start]到a[end]进行升序排序
● 例如,对a[0]到a[n-1]进行升序排序
sort( a, a + n);
注意sort函数的参数和排序范围的对应关系!

STL排序函数-功能图示

STL排序函数-降序排序

如何用STL排序函数进行降序排序?
● 方法:自定义比较函数,并作为sort的第三个参数

函数名可以自己定,符合命名规则即可

#include<algorithm>boolcmp(inta,intb){//函数功能:如果第一个参数排在第二个参数前面,返回true,否则返回falsereturna>b;}sort(a+start,atend+1,cmp);//注意:这里不需要对比较函数cmp传参数

● 以上可以实现a[start]到a[end]的降序排序
●当cmp省略时,sort函数进行升序排序

STL排序函数(总结)

#include<algorithm>sort(atstart,atend+1,cmp);

● 对数组a从a[start]到a[end]进行排序

●cmp是指自定义的比较函数,可省略

●cmp省略时,默认将数组a的内容从小到大(升序)排序

● STL排序函数通常是以快速排序为基础实现的,所以是不稳定的排序

● STL排序函数的时间复杂度是O(nlogn)

STL排序函数(总结02)

可以用STL排序函数为什么还要学排序算法呢?

● 排序是基础算法,原理非常重要

● 考级和竞赛可能会考到排序算法的原理

● 有的题目需要活用排序算法原理才能解决,需要深刻理解

● 当然,实际中遇到只需要排序的情况,可以简单地调用sort函数

去重函数unique

STL去重函数

C++的STL算法库还提供了去重函数unique
功能:对已经排序的序列进行去重
使用方法示例:

#include<algorithm>sort(a,a+n);intcnt=unique(a,a+n)-a;//注意sort函数的参数和unique函数的参数一般需要保持一致!

· 用到头文件 #include
· 必须先排序,后使用unique,否则不能完成去重功能
·unique返回的地址减去首地址(第一个参数)得到去重后的元素个数cnt

STL去重函数-过程演示

练习

明明的随机数

明明想在学校中请一些同学一起做一项问卷调查,为了实验的客观性,他先用计算机生成了
N个1到1000之间的随机整数(N <= 100),对于其中重复的数字,只保留一个,把其余相同的数去掉,不同的数对应着不同的学生的学号。然后再把这些数从小到大排序,按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。
【输入】有2行。第1行为1个正整数N,表示所生成的随机数的个数。第2行有N个用空格隔
开的正整数,为所产生的随机数。
【输出】2行。第1行为1个正整数M,表示不相同的随机数的个数。第2行为M个用空格隔开
的正整数,为从小到大排好序的不相同的随机数。

思路

使用STL排序函数、去重函数实现

1. 输入n个数到数组a (存放到a[0]~a[n-1])
2. 用sort(a,a+n)排序
3. 用unique(a,a+n)去重,同时得到去重后的元素个数cnt
4. 输出cnt
5. 输出排序、去重后的所有值

#include<iostream>#include<algorithm>usingnamespacestd;intmain(){inta[100]={0}