每日激励：“命运不是运气，而是选择。”
绪论：
本章是复习篇：基础的排序是我们面试的必不可少的一块本章首先先对排序有一定的了解，然后再从简单基础的插入排序、以及一个交换排序的冒泡排序开始学习，后面还将继续更新更多的排序算法，敬请期待！
————————
早关注不迷路，话不多说安全带系好，发车啦（建议电脑观看）。
排序前导
什么是排序？ 以及 一些排序中的基本概念！
- 排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
- 稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r [ i ]=r [ j ]，且 r [ i ] 在 r [ j ] 之前，而在排序后的序列中，r [ i ] 仍在 r [ j ] 之前，则称这种排序算法是稳定的；否则称为不稳定的。
- 内部排序：数据元素全部放在内存中的排序。
- 外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序
创建的排序算法（他们都是内部排序）：
1. 插入排序
核心思想：
在有序数组中插入元素，从后往前比较，直到找到第一个把他小的元素，此处下一个位置就是所要插入的位置
举例解释：
假设有n个元素前n-1个元素已经有序，现在要插入第n个元素
设n为5：有4个元素已经排好序了（如：1 2 4 5 ） ，现在要插入第5个元素(3)
那么就从后往前比较，找到第一个比他小的元素
很容易的就能找到是2的位置，所以就插到2下一个位置（得到 1 2 3 4 5）
在编程中可以注意的细节：
- 在向前比较的过程，可以顺便进行交换位置，这样就不断的把大的元素往后推，当找到第一个比他小的时候，也就直接完成排序了（此时就不用再次交换位置）
- 附：直接说可能有点抽象，可以有个影响，看代码更好理解！
代码（更多的细节已经注释好了，一定要再次通过代码才能更好的理解！）：
voidInsertSort(std::vector<int>& arr){//从第2位值开始往后遍历（默认第一位是排好序的），不断的插入只到最后//这样就能把无序的数组，逐渐变成有序，因为每一次就会将数组前i位的数值排序好//从第二位开始，只到最后（因为是下标他是从0开始的（不是1）所以数组内的元素个数-1，才是最后位置的下标）for(int i =1; i <= arr.size()-1; i++){//开始主要操作：//找第一个比当前插入元素小的元素for(int j = i; j >=1; j--){if(arr[j]< arr[j -1]){//如果当前元素比他小，那么不断向前移动
std::swap(arr[j], arr[j -1]);//此处的交换，就是不断往前移，并且把大的往后移}else{//当找到第一个比他小的，就停止了，也就走到了他自己的位置！！break;}}}}
分析代码：
- 时间复杂度：O(N2)
- 空间复杂度：O(1)
- 稳定排序（当遇到小于等于的就不交换，所以稳定！）
2. 希尔排序
希尔排序的由来：
希尔排序就是优化后的插入排序（为啥这么说？让我们接着往下看）
插入排序的优点是当遇到几乎已经排好序的数组时，其效率就会大大增加，因为不需要过多的比较，那么希尔排序就对此进行处理。
核心思想：
通过一个gap值，让相隔gap距离的看成一组数据先进行插入排序，这么就能大概率的将一些比较小的值快速的插入到前面。
举例解释：
有数组：10 5 7 8 2 4 1
此时假设使用插入排序，当插入1的时候，他将比较的次数将是n-1次。
而假设我们使用希尔利用gap将相差gap距离的值看成一组再进行插入排序
如：gap = n / 2 = 3（n 元素个数 7） 那么 10 8 1 看成一组、5 2 看成一组（后面没数据就不用）、7 4 看成一组。
那么当 10 8 1 这一组进行插入排序后 就将得到 ： 1 8 10 、
其他组将得到： 2 5 、4 7 一轮希尔排序：1 2 4 8 5 7 10（这样一来就几乎接近有序）
再如下面例子：
上述所有过程也称希尔排序的预排序
这样通过修改gap值不断的预排序，直到gap为1时进行正常的插入排序，就能完成希尔排序
编程中注意的点：
- gap的值一般我们从 n / 2开始，然后不断 / 2，这样最终一定能变成1，而变成1，也就是把间隔1的看成一组，那么就等于是把所有元素看成一组进行正常的插入排序，因为预排序的原因，就能大大提高插入排序的效率。
- 其中本质就是在插入排序上，再嵌套一个gap值来进行数组的分组，进行插入排序
- 注意的是在插入排序处需要修改for循环中的条件i < n - gap（n - gap：找到最后一个位置的下标），可以把gap看成1时来理解，此时就是正常的插入排序的写法了。
代码（上面注意的点直接看还是有点难理解，具体看代码就能更好的理解了！）：
注：在看之前一定要看之前的插入排序。
voidShellSort(std::vector<int>& arr){//最外层循环控制gapfor(int gap = arr.size()/2; gap >0; gap /=2){//i = gap 就等于是从第二个位置开始，arr.size() - gap 用于找最后一个元素！for(int i = gap; i <= arr.size()- gap; i++){//内部主要就是对给到的值 进行插入排序操作，只需要注意的是 我们是以gap距离为一个组，所以-=gap，找到同一组进行排序！for(int end = i; end >= gap; end-=gap){if(arr[end]< arr[end - gap]){//如果当前元素比他小，那么不断向前移动
std::swap(arr[end], arr[end - gap]);//此处的交换，就是不断往前移，并且把大的往后移}else{//当找到第一个比他小的，就停止了，也就走到了他自己的位置！！break;}}}}}
3. 冒泡排序
核心思想：
通过不断的交换，完成进行排序
具体如下：
每一次都从最开始往后不断比较遍历，比较后若该值大的则往后交换移动，这样一次遍历下来就能把最大的挪到最后，并且这样每一次遍历也就一定能把最大的数据最终交换到最后，从而排序好一个数。
通过最多n-1次的遍历，最终就能排序完成。
在编程中可以注意的细节：
- 因为是比较问题，访问数组时不能越界。此处是从 j 位置 与其 j + 1 的位置处比较，所以不需要去到达最后一个元素，因为最后元素 j 在 加1 的话，就会越界。
- 其中 - i 的原因：也就是核心逻辑中每一次变量就排序完成了的1个元素，将他减去，不需要遍历到后面比较了
代码：
void BubbleSort(std::vector<int>& arr) {
//执行n-1次最多(不要直接想，结合内部逻辑)for(int i =0; i < arr.size()-1; i++) {
//主要目的遍历数组//每一次都从头开始，然后不断往后比较，若大就给他交换到后面//这样每次都一定能 将最大的放到最后，排序完成一个元素for(int j =0; j < arr.size()- i -1; j++) {//注意还需要 -1 因为j和j+1位置比较不能越界if(arr[j]> arr[j +1]) {
std::swap(arr[j],arr[j+1]);//若j位置大，则交换到后面//这样假设j位置一直最大，最终就会移动到最后，反值其他也一样
}
}
}
}
本章完。预知后事如何，暂听下回分解。
如果有任何问题欢迎讨论哈！
如果觉得这篇文章对你有所帮助的话点点赞吧！
持续更新大量C++细致内容，早关注不迷路。
版权归原作者 溟洵 所有， 如有侵权，请联系我们删除。