排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，这里八大排序就是内部排序，指直接插入，希尔，选择，堆排，冒泡，快排，归并，计数。
下面让我们来共同学习这八大排序吧！🤗🤗🤗
什么是外部排序：
外排序是数据量较大,内存放不下,数据放到外部磁盘空间,一般使用归并排序进行外排序
假设内存为512m,给10亿个数据,然后内存每次读取512m的数据,排序完成后返回给磁盘,然后重复这个过程,直到拍完,然后外部的小文件,再经过归并,即可得到一个有序的数据.
目录
概述
一、插入排序
1、直接插入排序
2、希尔排序
二、选择排序
1、直接选择排序
2、堆排序
三、交换排序
1、冒泡排序
2、快速排序
2.1 hoare版本
2.2 挖坑法
2.3 前后指针法
2.4 快排非递归版
四、归并排序
1、归并排序递归版
2、递归排序非递归版
五、计数排序 - 非比较排序
六、对排序的分析总结
什么是排序的稳定性：
排序算法复杂度及稳定性总结：
基本思想：
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中（我们假设有序），直到所有的记录插入完为止，得到一个新的有序序列。就像是我们玩扑克牌时按顺序大小整理好牌的过程
动图展示 ：
实现代码：
相关分析 ：
对于插入排序：
时间复杂度
- 最坏：逆序 （计算类似等差数列） --O(N^2)
- 最好：顺序 （数据有序） ---O(N)
待排序元素集合越接近有序，直接插入排序算法的时间效率越高
希尔排序是1959 年由D.L.Shell 提出来的，相对直接插入排序有较大的改进。希尔排序又叫缩小增量排序.。希尔排序是对直接插入排序的优化。
基本思想：
- 希尔排序 = 预排序（分组插入排序） + 直接插入排序（最后一次为整体排序）
- 我们先选定一个整数gap，间隔为Gap的数据为一组,然后对这组数据进行排序（预排序）,再分组,再排,直到数组被分完.
- 将Gap减小,继续分组,排序.
- 最后Gap设为1,此时数据基本有序，即进行直接插入排序,得到有序数组
动图展示：
代码实现：
相关分析：
- 希尔排序对直接插入排序的优化在于：优化了直接插入排序对逆序数据排序效率很差的缺点。我们将数据进行了一个gap分组，然后进行组预排序，这样下来数据会越来越接近有序，等到最后一次排序的时候，我们无需进行大量的数据遍历，只需遍历个别不满足升序的数据即可。这样希尔排序效率就会比直接插入排序高很多。
- 对于希尔排序的时间复杂度：计算是不好计算的，需要进行数学推导，推导出来平均时间复杂度： O(N^1.3—N^2）
基本思想：
每次将数组遍历一遍，在数组[0,n]中选取最小（最大）的数,存放在序列的起始（或者末尾）位置，在[1,n-1]再次遍历选取,交换,缩减,直到全部待排序的数据元素排完
优化版：每次遍历待排序数据找出最大和最小的数据，分别排列到序列起始和末尾
动图展示：
代码实现：
相关分析：
直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用。其稳定性也较差
基本思想：
学过二叉树我们知道堆排序是指利用堆（数据结构）进行选择数据的一种排序算法。在已经建好堆的情况下，升序建大堆，降序建小堆，通过堆来选择数据,向下调整算法,得到小数(大数),然后再与堆底数据进行交换。每重新调整堆时，传给向下调整算法的数组个数要减1，数组的最后一个元素已经变得有序了，因此不需要我们调整了。
图示（大堆排序）：
代码实现：
相关分析：
- 堆排序使用堆来选数，效率就会高出很多
- 核心向下调整算法是实现排序的精髓，建堆同样用到
基本思想：
每次遍历待排序数组，对相邻数据进行比较，将值较大的数据向序列尾部移动，值较小的数据向序列前部移动。
动图展示：
代码实现：
相关分析：
我们可以做一个简单的优化，如果我们排序的某一趟每个元素都不用交换，则说明要排序的元素已经有序，那么后面的排序就可以直接跳出循环了。
2.1 hoare版本
基本思想：
我们将左边值设为key,然后右边right先走,找小的,比key小停下来,然后左边left走找比key大,然后交换左边右边，继续上述过程，直至left和right相遇，此时的值一定是比key小的值，我们再把key和这个相遇位置的值进行交换，此时key所在的位置，左边的数据一定比key值小，右边的数据一定比key值大，即key放到了合适的位置上。重复此过程进行递归，直至所有的元素都处在合适位置。
动图展示：
代码实现：
相关分析：
Hoare版本的快排需要注意的地方挺多的：
- 如果key后面的每个数都比key小或大的话，那left向后面找或right向前面找，会产生越界访问的问题，所以我们选择在if语句的判断部分逻辑与&&保证left小于right，以免产生越界访问的问题。
- 在if语句的判断部分，找的数据一定得比key小或大的。因为若相等会产生死循环。
对次的优化：
我们可以对key值的选取进行优化，采用三数取中法让我们选取的key数据在序列中的位置尽量靠中间，以提高递归的效率。同时，递归建立的栈帧数量会随着递归深度的增加而增加，为了避免递归深度太深，造成栈溢出的问题。我们采用小区间优化，当递归区间的数据量较小的时候，采用直接插入法进行排序。
相关代码：
2.2 挖坑法
基本思想：
挖坑法对hoare的思想进行了优化。我们设定key数组左边第一个值为坑,右边right找小,找到比key小的值填到坑位，right就成为新的坑位，然后左边left找大,找到后填到坑位上,left此时更新为新的坑位,循环此过程，right接着找小，left找大，交换形成新的坑位，直至left和right相遇。最后把key放到坑里，即类似于hoare版本key应处于的位置。
动图展示：
代码实现：
相关分析：
需要进行坑位的位置更新
2.3 前后指针法
基本思想：
我们定义两个指针cur和prev，选取key值,cur去遍历小于key的值,对prev++,交换cur与prev值,直至cur遍历完整个数组，prev位置的值一定是比key值小的，即key应处的正确位置
动图展示：
代码实现：
相关分析：
++prev!=cur 是对防止同一位置元素进行交换的简单优化，实际中，前后指针法推荐掌握，简单理解易于操控。
对前后指针法的优化：
在数据量极大的情况下，会出现很多相同的数据，此时进行快排，会建立很多栈帧，造成递归深度太深，运行时间过长，对于那些相同的数据我们采用三指针法进行优化
我们定义left，right，cur三个下标，利用cur对序列的遍历，找出大于key，等于key，小于key的三种值，将他们交换到left和right下标位置，将等于key值的数据集中到数组区间中部，然后继续递归剩余的左右区间，直至排序完成。
相关代码：
2.4 快排非递归版
基本思想：
对于非递归版的实现，因为递归函数在内存实际上是在栈中进行开辟函数栈帧，延用递归中的思想，这里我们采用数据结构中的栈来模拟内存中的栈，从而实现快排的非递归。
代码实现：
基本思想：
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。通过递归实现对小数组有序,再返回回来。
动图展示:
代码实现：
相关分析：
归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
基本思想：
因为递归实现过程就是分治,只不过非递归不用递归返回,我们可以不借助其他数据结构，直接对序列进行归并排序，这里主要采用循环：
相关分析：
对于越界情况我们可以直接break掉，拷贝的时候我们只能在for循环里面进行拷贝，也就是部分拷贝，防止在for循环外面进行拷贝的话，arr中会出现随机值的情况。
计数排序基本思想：
- 统计相同元素出现次数：在排序数组中找到最大最小的数据，算出对应范围（max - min +1）并创建对应长度个数组用来计数（相对位置遍历一次+1），遍历排序数组
- 根据统计的结果将序列回收到原来的序列中：根据每个出现的数据值与计数数组下标构建的相对映射关系进行统计数据出现次数，最后将统计的出的数据按次序赋值给原数组
- 我们总共需要遍历三遍数组
动图展示：
代码实现：
相关分析：
在数据较为集中的情况下，计数排序的性能是很好的，因为N大于range的话，其时间复杂度就是O(N)。缺点是：1、适用于数据集中的情况，数据分散会浪费空间 2、只适用于整型数据的排序
如果在某个排序算法在排序过程中，没有打乱原有序列中相同数据的相对位置关系，我们就称这个算法是稳定的。
像是希尔排序，相同的数据可能被预排序到不同的组，不能保证排序的稳定性；像是冒泡排序是从左到右进行比较排序，相同数据的相对位置关系不会发生改变，因此排序是稳定的。
总结：总体来说插入排序，选择排序，冒泡排序是低一级水平的排序算法，希尔排序，堆排序，归并排序和快速排序是高一级别的排序各有优缺点，最后计数排序效率非常高，但有一定局限性。