C++（STL排序函数）

学习目标STL排序函数STL去重函数计算机语言发展历史(三)第三代计算机语言是高级语言。用高级语言编写的程序易学、易读、易修改,通用性好,不依赖于机器。高级语言的发展分为两个阶段,以1980年为分界线,前一阶段属于结构化语言或者称为面向过程的语言,后一阶段属于面向对象的语言。例如C语言就是结构化的语言,而C++就是面向对象的语言。排序函数SortSTL算法库和算法●C++STL(标准模板库)是一套功能强大的库,它提供了丰富的数据结构和算法支持。● 其中algorithm(算法)库包含很多常用的算法,比如排序。● 熟练掌握STL算法的使用,可以让我们在编程过程中事半功倍。● STL算法一般以函数的方式提供STL排序算法(函数)在C++的STL中,提供了用于排序的函数sort,直接调用即可● 一般使用方法:#includealgorithm//必须包含的头文件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的第三个参数函数名可以自己定,符合命名规则即可#includealgorithmboolcmp(inta,intb){//函数功能:如果第一个参数排在第二个参数前面,返回true,否则返回falsereturnab;}sort(a+start,atend+1,cmp);//注意:这里不需要对比较函数cmp传参数● 以上可以实现a[start]到a[end]的降序排序●当cmp省略时,sort函数进行升序排序STL排序函数(总结)#includealgorithmsort(atstart,atend+1,cmp);● 对数组a从a[start]到a[end]进行排序●cmp是指自定义的比较函数,可省略●cmp省略时,默认将数组a的内容从小到大(升序)排序● STL排序函数通常是以快速排序为基础实现的,所以是不稳定的排序● STL排序函数的时间复杂度是O(nlogn)STL排序函数(总结02)可以用STL排序函数为什么还要学排序算法呢?● 排序是基础算法,原理非常重要● 考级和竞赛可能会考到排序算法的原理● 有的题目需要活用排序算法原理才能解决,需要深刻理解● 当然,实际中遇到只需要排序的情况,可以简单地调用sort函数去重函数uniqueSTL去重函数C++的STL算法库还提供了去重函数unique功能:对已经排序的序列进行去重使用方法示例:#includealgorithmsort(a,a+n);intcnt=unique(a,a+n)-a;//注意sort函数的参数和unique函数的参数一般需要保持一致!· 用到头文件 #include· 必须先排序,后使用unique,否则不能完成去重功能·unique返回的地址减去首地址(第一个参数)得到去重后的元素个数cntSTL去重函数-过程演示练习明明的随机数明明想在学校中请一些同学一起做一项问卷调查,为了实验的客观性,他先用计算机生成了N个1到1000之间的随机整数(N = 100),对于其中重复的数字,只保留一个,把其余相同的数去掉,不同的数对应着不同的学生的学号。然后再把这些数从小到大排序,按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。【输入】有2行。第1行为1个正整数N,表示所生成的随机数的个数。第2行有N个用空格隔开的正整数,为所产生的随机数。【输出】2行。第1行为1个正整数M,表示不相同的随机数的个数。第2行为M个用空格隔开的正整数,为从小到大排好序的不相同的随机数。思路使用STL排序函数、去重函数实现输入n个数到数组a (存放到a[0]~a[n-1])用sort(a,a+n)排序用unique(a,a+n)去重,同时得到去重后的元素个数cnt输出cnt输出排序、去重后的所有值#includeiostream#includealgorithmusingnamespacestd;intmain(){inta[100]={0}