戳一戳！和我一起走进信息学的世界
导读
信息学能够有助于孩子未来工作发展，提升孩子的综合能力。
从这一节课开始，我们正式走进算法的世界，一起感受算法的魅力。
今天要给大家讲的是排序算法。排序算法是很多种不同类别排序算法的总称，C++中也有专门的sort函数用于排序。我们今天的课程主要是让大家了解不同的排序算法，了解算法的思想。
往期回顾
?赛前必看！信息学名师带你复习NOIP竞赛初赛及CSP认证初赛?收藏！交流会内容全公开，让你陪孩子更好地学习信息学
?信息学的万般好处！附C++必备基础知识总结
?信息学提高班知识体系详解与家长常见问题解答！让孩子赢在提高班学习的起跑线！
?再回首，最全提高班知识总结，做更优秀的自己！
?早知道！信息学集训班大揭秘！你想知道的的都在这！
?01温故知新，以更好状态学习数据结构和算法?02信息学初赛必备计算机知识大串讲?03位运算与进制初步?04进制进阶与编码?05字符串进阶操作?06栈理论与实战?07队列理论与实战?08栈与队列实战?09算法及其复杂度?1温故知新——一篇文章领略信息学C++知识结构?2披荆斩棘——只学C++，可以做哪些竞赛题?3运筹帷幄——一篇文章，让指针学起来也很简单！?4初试锋芒——顺序表写起来也很简单?5小试牛刀——STL库之vector数组?6触类旁通——链表基本理论与信息学竞赛必考点?7更进一步——STL库之List链表?8知“人”善任——深入理解顺序表和链表的区别与应用
?C++强化01新学期再出发！温故知新！?C++强化
02继续前行，三大结构终极介绍?C++强化
03一维数组入门?C++强化
04数组越界?C++强化
05一维数组经典应用?C++强化
06一篇文章带你掌握字符数组?C++强化
07二维数组?C++强化
08二维数组经典案例?C++强化
09一篇文章带你探索函数的奥秘?C++强化
10函数进阶必备?C++强化
11这样学递归，才不会觉得难?C++强化
12格式化输入输出与文件操作?C++强化
13结构体入门?C++强化
14结构体进阶?C++总结
01程序的世界?C++总结
02输出、换行与注释?C++总结
03变量定义、赋值与运算?C++总结
04算术运算符与赋值运算符?C++总结
05cin语句?C++总结
06程序中的数据类型?C++总结
07数据类型补充?C++总结
08顺序结构?C++总结
09if和if-else?C++总结
10if嵌套与逻辑运算符?C++总结
11开关语句switch-case?C++总结
12for循环及其应用?C++总结
13数据范围与数据类型?C++总结
14break与continue?C++总结
15while与do-while?C++总结
16循环嵌套及其应用
1回顾
其实我们之前学数组和循环嵌套的时候，就学过了排序算法，让我们一起来回顾一下。
1排序算法实现
我们先来回顾一下之前讲得排序算法的思想。
比如我们有如下的一串数据：
我们想要让这串数据从小到大排序，我们可以每次都找到当前这个序列的最小值，放在最前面，然后再从第二个开始寻找，找次小值，放在第二个位置……
具体流程如下：
1、我们先让第一个数据和后面的每个数据做比较，如果第一个数据比后面的数据大，我们就让这两个数据交换位置。这种做法能够让每次比较中的最小值放在第一个位置。一直做上面的步骤，直到比较到最后一个数据，最小值就存放在第一个位置了。2、我们让第二个数据和后面的每个数据做比较，如果第二个数据比后面的数据大，我们就让这两个数据交换位置。这种做法能够让每次比较中的最小值放在第二个位置。一直做上面的步骤，直到比较到最后一个数据，次小值就存放在第二个位置了。3、依次类推，当我们比较到倒数第二个数据的时候，倒数第二个数据和最后一个数据比较一次即可。
代码如下：
#includeiostreamusingnamespacestd;intmain(){inta[9]={1,3,5,9,4,6,2,7,8};intt;for(inti=0;i8;i++){for(intj=i+1;j9;j++){if(a[i]a[j]){t=a[i];a[i]=a[j];a[j]=t;}}}for(inti=0;i9;i++){couta[i]"";}return0;}
2排序介绍
上面是一个非常基本的排序算法，接下来我们来看一下其他的排序算法！
1排序算法分类
排序算法主要分两大类，第一大类叫内部排序，第二大类叫外部排序。
内外部排序的区别在于，是否需要大量的内存，以至于需要外部存储介质协助存放数据。内部排序指的是只需要少量内存，不需要外部存储介质的帮助。我们一般的排序算法，也只考虑内部排序，在一些难度较大的竞赛中，也会涉及到一些外部排序的算法。这不是我们现在要考虑的。
内部排序主要分为如下几部分：
1、插入排序：直接插入排序、折半插入排序、希尔排序2、交换排序：冒泡排序、快速排序3、选择排序：简单选择排序、堆排序4、归并排序5、基数排序2排序算法指标
排序算法也属于算法，所以排序算法中两个非常重要的指标是时间复杂度和空间复杂度。除此之外，还有算法稳定性。排序算法的稳定性是指：排序数据中两个相等数据的位序在排序后位序不变。
3插入排序
首先我们先来看一下插入排序！
插入排序是指不断地将新的数据插入到已经排好序的序列中，并保证插入后的序列依然是有序的。
1直接插入排序
我们通过一个示例来理解直接插入排序：
例如有如下的一个序列：
0
我们考虑第一个数据，如果只有一个数据，那么这个数据就是有序的（逗号前面表示数据有序）：
1，
我们想把3插入，我们就从后往前插入，如果要插入的数据比序列中的最后一个数据小，就将最后一个数据后移。我们不断执行上面的操作，直到我们已经比较到的第一个元素，或者比较到某一个位置的元素比要插入的元素小。就在该位置的后面存这个数据。
所以上面的这一串数据，按照直接插入排序，插入流程如下：
1，1有序，将3插入，3比1（当前有序序列的最后一个元素）大，就放在该元素后面；当前序列为：13，有序，将5插入，同上；9同上当前序列为：，462780有序，将4插入，4比9小，9后移一位，4比5小，5后移一位，4比3大，放在3的后面当前序列为：，62780有序，将6插入，6比9小，9后移一位，6比5大，放在5的后面当前序列为：，同上。当前序列为：，0有序，0和所有的比较，每比较一次，有序序列中的元素后移一位。直到比较到第一个数据，前面没有数据，0放在第一个位置。2折半插入排序
上面的做法在比较的过程中，需要移动大量元素，也需要比较大量元素。
但是前面的已经有序了，我们就可以使用折半的思想，让比较的次数降低。上面的比较是从后往前依次比较。折半插入，是折半查找。
例如我们最后一个0想要插入，前面已经有了9个有序的元素，最大索引为8。那我们就和索引为8/2=4的元素（5）进行比较。0比5小，说明0应该在索引4的前面，那我们再和索引为4/2=2的元素（3）进行比较。0比3小，说明0应该在索引2的前面，那我们再和索引为2/2=1的元素（2）进行比较。0比2小，说明0应该在索引1的前面，那我们再和索引为1/2=0的元素（1）进行比较。0比1小，说明0应该在索引0的前面，已经到最前面，说明0就是最小。这个时候就找到了插入的位置，然后将该位置及之后的所有元素后移，然后将0插入。
整体来看，折半插入只是比较次数可能变少，但是移动的次数没有变化。
3希尔排序希尔排序是比较特殊的函数。希尔排序本质上也是为了优化排序的效率。
我们通过一个示例来了解希尔排序：
0
我们设置一个间隔为数组个数的一半，即为5。然后让索引为i和索引为i+5的数据进行比较，如果后面的数据小，就交换两个数据。
01---------63---------25---------79---------84---------0比较并交换后为1---------62---------35---------78---------90---------4第一趟比较后的序列为：
然后我们再缩小间隔为上一次间隔的一半（2）：
1---52---85---0（有交换）0---58---6（有交换）6---85---3（有交换）3---58---7（有交换）7---85---98---4（有交换）4---8第二趟比较后的序列为：
然后我们再缩小间隔为上一次间隔的一半（1）：
1-22-0（有交换）0-22-66-3（有交换）3-66-77-5（有交换）5-77-4（有交换）4-77-99-8（有交换）8-9第三趟比较后的序列为：
这个时候，就整体比较有序了，我们再结合其他的一些排序算法做最终的排序，就可以了。
希尔排序的作用就是尽快让序列有序，然后再结合其他的排序算法，因为有些排序算法，在序列相对有序的前提下，算法的复杂度可以由n2级别转化为接近n级别的。
4交换排序
接下来我们看交换排序！
交换排序就是通过不断交换两个元素实现排序的作用。
1冒泡排序
冒泡排序是最简单也很经典的交换排序。
冒泡排序就是不断比较相邻的两个元素，如果后面的元素比前面的元素小，那我们就交换两个元素。这个过程，就相当于不断冒泡的过程，我们将其称之为冒泡排序。
举个例子：
00（1和3比较，不交换）0（3和5比较，不交换）0（5和9比较，不交换）0（9和4比较，交换）（9和6比较，交换）（9和2比较，交换）（9和7比较，交换）（9和8比较，交换）（9和0比较，交换）
上面这是一轮的比较结果，这样的比较结果会把最大的放在最后面。下一轮，我们还是从第一个开始，直到倒数第二个结束，将次大值放在倒数第二个位置。以此类推，直到只剩下前两个位置，做比较并决定是否交换。
2快速排序快速排序在一般情况下是所有经典排序算法中最快的，所以称之为快速排序。快速排序使用了递归的思想。和折半插入排序思想有些类似。
0
我们直接通过例子来理解排序算法的思想：
我们随便选择一个元素，例如1（即序列中的第一个元素）。然后将比1小的放在1的左边，比1大的放在1的右边：
0
对于1的左边，只有0，就不用管了，对于1的右边，我们还采取上面的策略。1的右边序列如下：
我们选择第一个元素3，将比3小的放在3的左边，比3大的放在3的右边：
对于3的左边，只有2，就不用管了，对于3的右边，我们还采取上面的策略。3的右边序列如下：
我们选择第一个元素5，将比5小的放在5的左边，比5大的放在5的右边：
对于5的左边，只有4，就不用管了，对于5的右边，我们还采取上面的策略。5的右边序列如下：
我们选择第一个元素9，将比9小的放在9的左边，比9大的放在9的右边：
然后我们只用考虑9的左边，第一个元素为6，78都在6的右边，考虑78，对于7来说，8在7的右边。
上面是递去，接下来是归来，78有序，返回到6，有序，返回到9，有序。返回到5，45有序。返回到3，2345有序。返回到1，0有序，归来结束。
5作业
本节课的作业，就是复习上面的所有知识，并完成下面两道题目！
1代码实现直接插入排序
根据算法思想，实现直接插入排序。
2代码实现冒泡排序根据算法思想，实现冒泡排序。
AI与区块链技术
长按