导读
信息学能够有助于孩子未来工作发展，提升孩子的综合能力。
前面两节课，我们学了排序算法，这一节课我们来分析一下排序算法，并了解一下sort函数的用法吧！
1 排序算法回顾
前面我们学了所有基本的内部排序算法，现在我们可以对内部排序算法做个总结了。
内部排序算法总的来说可以分为如下几类：
插入排序
交换排序
选择排序
二路归并排序
基数排序
具体内容，就看下面的两篇文章吧！
2 排序算法的评价指标
回顾完排序算法，接下来我们看一下排序算法的评价指标，前面我们讲算法的评价指标有时间复杂度和空间复杂度，对于排序算法，我们还有一个指标，叫做稳定性。我们也要考虑排序算法适用于链式存储结构还是顺序存储结构。
1 稳定性与适用性
稳定性的概念如下：
假设在 (1≤i≤n,1≤j≤n,i≠j)，排序前的序列中 领先于 ，若在排序后的序列中 仍领先于 ，则称所用排序方法是稳定的，若在排序后的序列中 可能仍领先于 ，则称所用排序方法是不稳定的。
举个例子，例如下面的三个数：
1，2，2
如果排序之后变成了如下：
1，2，2
那我们就说这个排序算法是不稳定的，因为两个2交换了先后顺序。
2 时间与空间复杂度
时间复杂度和空间复杂度和前面讲的是一样的。具体可以看：
对于排序算法来说，因为我们考虑的是级别（如，指数级），所以对于时间复杂度，我们一般从循环次数来考虑，而且要考虑最好时间复杂度、最坏时间复杂度、平均时间复杂度。对于空间复杂度，从需要额外的空间来考虑。
3 不同排序算法的评价
了解了评价指标，我们就来具体看下每个算法吧！当然，评价之前，一定要先了解每个算法的思想哦！
在最前面，我们用一张图来总结一下：
1 直接插入排序
直接插入排序分析如下：
1、稳定性
直接插入排序是将后面元素插入到前面有序的序列中，如果发现和某一个一样，就会放在该元素的后面，不会发生相同元素前后位置变化的情况。
2、最好时间复杂度
在最好的情况下，表中元素已经有序，每一个元素在排序的时候，和已经有序的最后一个比较一次，就可以了，不需要移动元素，所以时间复杂度为O(n)。
3、最坏时间复杂度
在最坏的情况下，表中元素是逆序存储，每一个元素在排序的时候，都要和前面每个元素比较一次，每比较一次，就需要移动一次元素，所以时间复杂度为
4、平均时间复杂度
平均时间复杂度就是考虑待排序序列的元素是随机的，所以平均时间复杂度我们取最好和最坏的平均值，即 ，所以，平均时间复杂度为O(n²)。
5、空间复杂度
在排序过程中，我们仅需要一个额外的辅助空间，用来暂存要排序的数据，所以空间复杂度为O(1)。
6、适用性
直接插入排序是顺序遍历整个序列，所以适用于顺序结构和链式结构的线性表。
2 折半插入排序
折半插入排序和直接插入排序的区别在于找位置的过程，折半插入排序查找位置是根据索引跳着查找，但移动元素的过程和直接插入完全一样。具体如下：
1、稳定性
和直接插入一样，是稳定的。
2、最好时间复杂度
和直接插入一样，最好时间复杂度为O(n)。
3、最坏时间复杂度
在最坏的情况下，比较次数是折半比较，这种不断折半的复杂度为 ，一共有n个元素，所以查找位置的复杂度为
4、平均时间复杂度
比较查找的复杂度和最坏的一样，是 ，插入的平均时间复杂度为O(n²)。
5、空间复杂度
在排序过程中，我们仅需要一个额外的辅助空间，用来暂存要排序的数据，所以空间复杂度为O(1)。
6、适用性
由于查找过程是跳跃的，更适用于可以直接通过索引访问元素的顺序表。
3 希尔排序
希尔排序分析如下：
1、稳定性
希尔排序是不稳定的，举个例子，将下面的这组数据从大到小排序：
1，2，2
首先我们让排序间隔为2，那么1和后面的2就会交换位置，但是中间的2不动，这样排序的结果为：
2，2，1
然后排序间隔为1，排序结果不变。序列有序。这个时候我们发现，两个2交换了前后位置。
2、时间复杂度
希尔排序的时间复杂度依赖间隔的选择，我们直接了解结论即可：当n在某个范围内，其时间复杂度约为 ，最坏时间复杂度为O(n²)。
3、空间复杂度
在排序过程中，我们仅需要一个额外的辅助空间，用来暂存要排序的数据，所以空间复杂度为O(1)。
4、适用性
因为需要跳跃对比，希尔排序只适用于顺序表。
4 冒泡排序
冒泡排序分析如下：
1、稳定性
两个相邻元素比较做交换，如果相等就不会交换，所以冒泡排序是稳定的。
2、最好时间复杂度
最好情况下，序列有序，经过一趟排序并没有元素交换，只比较n-1次，最好时间复杂度为O(n)。
3、最坏时间复杂度
在最坏的情况下，是逆序，每次比较都要移动，和插入排序一样，所以最坏时间复杂度为O(n²)。
4、平均时间复杂度
和前面的直接插入排序思想一致，平均时间复杂度为O(n²)。
5、空间复杂度
在排序过程中，我们仅需要一个额外的辅助空间，用来暂存要排序的数据，所以空间复杂度为O(1)。
6、适用性
比较相邻的两个元素，也不需要随机存取，所以适合顺序表和链表。
5 快速排序
快速排序是内部排序算法中平均性能最优的算法。分析如下：
1、稳定性
快速排序是不稳定的，举个例子，将下面的这组数据从大到小排序：
1，2，2
从1开始，两个2都放1的左边，可能会交换位置，这样排序的结果为：
2，2，1
所以不是稳定的。
2、时间复杂度
最好情况下和平均情况下，序列能对半分，则复杂度为 。最坏情况下，序列有序，每次排序，剩余所有的元素都在同一侧，那么时间复杂度为O(n²)。
3、空间复杂度
平均来说和最好情况下，每排序一次，就要生成一层递归，那一共就是 。在最坏情况下，就是前面说的有序，就是O(n)。
4、适用性
顺序结构和链式结构都适用。
6 简单选择排序
简单选择排序分析如下：
1、稳定性
简单选择排序是不稳定的，举个例子，将下面的这组数据从大到小排序：
2，2，1
2和2比不交换，但是和1相比交换，则序列变为：
1，2，2
2、时间复杂度
因为简单选择排序是每一个都要和后面所有的比较，所以不管序列什么样，复杂度永远都是O(n²)。
3、空间复杂度
在排序过程中，我们仅需要一个额外的辅助空间，用来暂存要排序的数据，所以空间复杂度为O(1)。
4、适用性
因为要和后面的每个作比较，最好是用顺序表，用链表的话，要保存当前位置的指针。
7 堆排序
堆排序分析如下：
1、稳定性
堆排序要分不同的叉，可能在不同的叉上，就会使得输出顺序改变，例如：
1，2，2
1先输出，2在最后，放到根的位置，和2比不交换，输出，最后2输出，即输出序列为：
1，2，2
所以堆排序不稳定。
2、时间复杂度
堆排序要先构建堆，构建的时间为O(n)，然后每次输出一个需要调整堆，调整的复杂度即为堆的深度h，所以调整的时间复杂度为O(h) = 。所以时间复杂度为 。
3、空间复杂度
在排序过程中，我们仅需要一个额外的辅助空间，用来暂存要排序的数据，所以空间复杂度为O(1)。
4、适用性
适用于树形结构。
8 二路归并排序
归并排序分为二路归并和多路归并，多路归并是外部排序算法，我们不考虑。
1、稳定性
二路归并排序是从前往后排序，合并过程中，并不会交换相同元素的位置，所以是稳定的。
2、时间复杂度
每一趟归并的时间复杂度为O(n)，一共需要 次合并。所以时间复杂度为
3、空间复杂度
归并过程中，需要n个辅助空间，所以空间复杂度为O(n)。
4、适用性
顺序结构和链式结构均可。
9 基数排序
基数排序分析如下：
1、稳定性
基数排序是按照数位排序，数位相同的两个元素不交换位置，所以总的也不会交换，所以是稳定的。
2、时间复杂度
基数排序需要d趟分配（d是数位），以r为基数，一共有n个数据，那么时间复杂度为O(d(n+r))。
3、空间复杂度
需要r个队列辅助存储，空间复杂度为O(r)。
4 sort函数
了解了算法性能分析，一方面是为了更深入了解算法，另一方面是为了初赛！
在实际应用中，我们可以直接使用sort函数实现排序，会更加方便。
1 sort函数介绍
sort函数需要用到头文件：
#include < algorithm >
用法如下：
sort（首地址，末地址，排序规则）
例如我们要对数组a[]排序，就可以这样写。
sort（a+m，a+n，排序规则）
这个就是对数组a中，从索引为m的元素开始，一直到索引为n-1的元素为止的所有元素进行排序。
2 sort函数排序规则
了解了sort函数，我们来了解一下sort的排序规则：
1、默认排序规则
默认排序规则，就是函数的第三个参数不写。排序结果为从小到大排序。
例如：
执行结果如下：
2、自定义排序规则
我们可以自定义排序规则，例如从大到小排序：
#include<iostream>
#include<algorithm>
using namespace std;
bool cmp(int x, int y){
return x>y;
}
也就是说x和y两个数比较，如果x>y，那么就返回真，否则返回假，排序会按照真的结果排序，所以排序就是把大的放前面，把小的放后面，也就是从大到小排序了。
具体在sort函数中的使用就是直接将cmp写在第三个参数位置即可，具体如下：
int main(){
int a[5] = {3,1,5,4,2};
sort(a, a+5, cmp);
cout<<"排序后的结果为："<<endl;
for(int i = 0; i < 5; i++){
cout<<a[i]<<" ";
}
return 0;
}例如，我们想实现偶数放前面，奇数放后面，然后再按照从小到大排序，那么规则就可以如下：
如果同为奇数或者偶数，小的放前面，即返回 x<y;
否则偶数放前面，即返回 x%2 < y%2;
代码如下：
#include<iostream>
#include<algorithm>
using namespace std;
bool cmp(int x, int y){
if(x%2 == y%2) return x<y;
else return x%2 < y%2;
}
int main(){
int a[5] = {3,1,5,4,2};
sort(a, a+5, cmp);
cout<<"排序后的结果为："<<endl;
for(int i = 0; i < 5; i++){
cout<<a[i]<<" ";
}
return 0;
}
3、对结构体数组排序
对结构体数组排序一般是根据结构体的某几个成员进行排序。例如：
按照总分从大到小排序
如果总分相同，按照语文成绩从大到小排序
代码如下：
#include<iostream>
#include<algorithm>
using namespace std;
struct Student{
int total,chinese;
} s[10];
bool cmp(Student s1, Student s2){
if(s1.total == s2.total)
return s1.chinese > s2.chinese;
else
return s1.total > s2.total;
}
int main(){
for(int i = 0;i<10;i++){
cin>>s[i].total>>s[i].chinese;
}
sort(s, s+10, cmp);
cout<<"排序后的结果为："<<endl;
for(int i = 0; i < 10; i++){
cout<<s[i].total<<" "<<s[i].chinese<<endl;
}
return 0;
}
例如我们用下面的数据：
200 100
195 95
195 96
195 98
150 52
164 74
165 86
165 88
180 92
174 74
执行结果如下：
5 作业
本节课的作业，就是复习上面的所有知识，并完成下面两道题目！
1 整数排序
使用sort函数进行排序，要求如下：
输入十个整数，进行排序；
奇数放前面，偶数放后面；
大数放前面，小数放后面。
2 结构体排序
使用sort函数进行排序，要求如下：
某个班有十名同学，输入总成绩（大于语文和数学成绩之和）和语文数学成绩。
按照考试总成绩从低到高排序；
总成绩相同，按照语文成绩从低到高排序。
语文成绩也相同，按照数学成绩从低到高排序。
AI与区块链技术
长按二维码关注