本文主要讲解代码及代码思路，涵盖八大排序的全面知识点
————————————————
目录
一、直接插入排序
二、希尔排序(直接插入排序的改良版)
三、选择排序（直接选择排序）
四、堆排序
五、冒泡排序
六、快速排序
1、 左右指针法
2、挖坑法：
3、前后指针法：
4、快速排序的非递归实现
七、归并排序
1、归并排序的递归实现
2、归并排序的非递归实现
八、计数排序
九、总结：
排序 ：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中， r[i]=r[j] ，且 r[i] 在 r[j] 之前，而在排序后的序列中， r[i] 仍在 r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。数组中相同值，排完序相对顺序可以做到不变就是稳定的，否则就不稳定。
稳定性还是重要的，因为比如考试中给班级前三名同学颁发奖品，如果现班级前几名分数依次为100,99,96,96,96,那三个96我们肯定认为谁先交谁就是第三名，如果这个排序稳定，那就是公平的，如果不稳定，就可能造成不公平，后交的变成了第三名。
那么判断这个排序是否稳定可以看如果数组中有相同值，相同值会不会换，主要依靠的就是对应排序的思想。
内部排序 ：数据元素全部放在内存中的排序。外部排序 ：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
原理：在数组前面已经是升序下，插入一个数据，让数组重新变为升序该怎么做。
2、整体复合排序
原理：既然单趟排序是利用已存在升序原理做的。那我们就对整个数组从头开始都假设升序然后插入一个数据。
3、直接插入排序的时间复杂度和空间复杂度：
时间复杂度：O(N*N)
插入排序的时间复杂度可以通过分析算法的执行过程来计算。在最坏的情况下，即待排序的数组是逆序排列的情况下，插入排序需要比较和移动元素的次数最多。
假设待排序数组的长度为 n。在插入排序中，我们从第二个元素开始，依次将每个元素插入到已排序的子数组中。为了将当前元素插入到正确的位置，我们需要将其与已排序子数组中的元素进行比较，并移动比它大的元素。
在最坏情况下，每个元素都需要与其前面的所有元素进行比较，并且可能需要移动整个已排序子数组。因此，对于第 i 个元素，需要比较 i-1 次，并且可能需要移动 i-1 次。
假设移动一个元素需要花费 O(1) 的时间，比较两个元素也需要花费 O(1) 的时间。在最坏情况下，对于第 i 个元素，我们需要比较和移动 i-1 次。所以总的时间复杂度可以表示为：
T(n) = 1 + 2 + 3 + ... + (n-1) = (n-1) * n / 2 = O(n^2)
因此，插入排序的时间复杂度为 O(n^2)。需要注意的是，这只是最坏情况下的时间复杂度，而在最好情况下，即数组已经是有序的情况下，插入排序的时间复杂度为 O(n)。
空间复杂度: O(1)
稳定性：稳定 因为排序完数组中相同的值相对位置不变
1、希尔排序概念
希尔排序法又称缩小增量法。希尔排序法的基本思想是： 先选定一个间距gap，把待排序数据中所有数据分成个 组，所有距离为gap的记录分在同一组内，并对每一组内的数据进行排序。然后，重复上述分组和排序的工 作。直到当gap =1 时，再排序，排完就有序了 【 注意：gap是组内每个数据的间隔 】
2、为什么要引入希尔排序？
在直接插入排序的基础上进行优化，效率更高，如果数据很多，我们是需要这个效率的
那直接插入排序的效率：顺序有序最好O(N) ，逆序最坏，越接近有序，效率越好。
但直接插入排序本身并不知道数组是有序还是逆序，效率有不确定性，在此之上，希尔提出了优化的方式。
3、希尔排序：
①、预排序（使数组接近有序）:gap>1用来预排序，因为预排序后基本就会接近有序
②、直接插入排序：预排序后gap=1用来直接插入排序。
把间距为gap的值分为一组，进行插入排序
gap越大，前面大的数据可以越快到后面，后面小的数，可以越快到前面，但gap越大，越不接近有序。
gap越小越接近有序，当gap=1时其实就相当于直接插入排序，就有序了。
大体步骤：
对于一组的预排序应该如下：
多组并排（希尔排序完整代码）：
对于多组并排我们想的肯定是一组一组排序，但人们之前就想到更好的代码，可以一下把所有间距为gap的所有组的排序都排完，从end=0开始，排的是一组，排完后end++排的可能就是另一组，因为有间距gap。（循环条件 i < n - gap,每次循环再i++ 就可以实现一趟把所有组都排一遍，最后end会=n-1-gap，这正是最后一组数据的倒数第二个元素，那此时插入完最后一组的最后一个数据a[end+gap]后，所有组数据就排完了 ）
理解为什么循环条件i < n - gap就可以实现把所有组排一遍了：
问题解释：
①、for循环的添加可以实现从一组的预排序到多组的排序
②、gap每次循环 gap = gap / 3 + 1是经过测试和预算，针对各种场景基本最佳的代码，有利于预排序排成有序，当然有的人会用gap /= 2，但没有gap = gap / 3 + 1优化 ,gap不断缩小的目的是为了更加有序，因为更加有序的直接插入排序效率高。
③、循环进行条件是gap > 1，gap > 1就会进行预排序，gap=1本质上就是直接插入排序，而gap=1一定会进行一次的，因为gap=gap/3+1
希尔排序的时间复杂度：
希尔排序的时间复杂度不好计算，因为 gap的取值方法很多，导致很难去计算，希尔排序的时间复杂度并不固定时间复杂度为O(N^1.3 ~ N^2)，一般情况下优于插入排序，但在本来有序的情况下插入排序就比希尔排序效率高，但这种情况很少。
空间复杂度：O(1)
稳定性：不稳定
思想：
我们一般用的是一次选出一个最大值或最小值，但我们可一次选出两个值，一个最大值，一个最小值来提高效率（最小值放在第一位，最大值放在最后一位）。选出两个值后左右指针begin++,end--即可，用来忽视上一次选出的最大值和最小值，在新的区间再次找最大值和最小值，并再次将最大值放开头，最小值放末尾......
问题：
如果最大值一开始就在区间的开头，而每次区间的最小值都会放到开头的，可最大值在最小值放在开头后，还要放到末尾，可此时最大值已经被覆盖，他被换到了a[minimal]的位置了（因为Swap(&a[begin], &a[minimal]);），所以如果begin==maximal(即最大值一开始在开头)，maximal应=minimal
下列代码中Swap函数是利用指针交换两个元素
时间和空间复杂度：
时间复杂度：O（N^2）
因为第一次需比较n-1次，第二次n-3，第三次n-5次以此类推，就是个等差数列，利用等差数列前n项和公式就知道为O(N^2)
但是直接选择排序的效率不是很高，不管数组如何都会那么排，对于巧合，比如本就是升序的情况，还是会那么排，实际应用中我们不常使用
空间复杂度：O（1）
稳定性：不稳定
堆排序在我的另一篇博客堆的讲解中有详细讲过，这里不过多赘述
【数据结构】堆的实现（向下调整和向上调整法）和堆排序的实现_堆的调整算法-CSDN博客
时间和空间复杂度：
堆排序使用堆来选数，效率就高了很多。时间复杂度：O(N*logN)空间复杂度：O(1)稳定性：不稳定
冒泡和快速排序都是交换排序
交换排序基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，其特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动
思路：
比较基础，两个两个比，最后把最大的放最后（或把最小的放最前）即可。但有一种情况:如果在第一次比较中，一次都没交换说明已经有序了，故利用标志性flag来判断是否有序
时间复杂度和空间复杂度：
时间复杂度：O（N^2）
n-1+n-2+n-3+......还是一个等差数列，所以是O (N^2)
空间复杂度:O（1）
稳定性：稳定
快速排序分为单趟排序和整体排序
单趟排序有三种方法：
1、左右指针法
2、挖坑法（左右指针法的变形）
3、前后指针法
三种方法只是写法上的差异，性能没有差别
单趟排序的思路（假设排升序，n为数组元素个数）：
选定一个基准值（数组中的值）Key，通常会选第一个值或最后一个值都可以，然后会设置两个值begin=0，end=n-1，即begin和end都为数组元素下标，begin从左往右走，end从右往左走，begin找比Key大的值(a[begin])，end找比Key小的值(a[end])，（若begin和end遇到和Key相等的值，要继续走，因为与Key相等的值在Key的左边还是右边无所谓，但主要因为没这个条件，begin和end就无法往下走）且会一直找，end和begin找到后两者(a[begin]和a[end])交换即可，一直找并交换，直到begin和end重合，再把key与两者重合的那个值交换，交换后key的左边就是比key小的，右边就是比key大的。
要点：
①、左边要比Key要小，右边比Key大
②、Key要放到他正确的位置（最终要放的位置）
③、Key设置为第一个值还是最后一个值的区别仅在于begin先走还是end先走
选取最后一个数为基准值，则一定要begin先走，因为左边先走能保证最后落的位置比Key要大（然后key会与重合位置交换），因为我们想让在Key右边的值都比Key大，而begin就是用来找比Key要大的，在最后一次要重合时，begin停下来的位置一定比Key要大，而end受到循环条件begin<end的束缚，即使找不到<=Key的，最后也会落到和begin相同的位置
选取第一个数作为基准值，则一定要end先走，因为右边先走能保证最后落的位置比Key要小，因为我们想让在Key左边的值都比Key小，而end就是用来找比Key要小的，在最后一次要重合时，end停下来的位置一定比Key要小，而begin受到循环条件begin<end的束缚，即使找不到>=Key的，最后也会落到和end相同的位置
若不这么做，就可能导致Key的右边存在比Key小的，Key的左边存在比Key大的
图解左右指针法的单趟排序的过程 ：
问题解决：
代码中begin和end走的前提是begin<end，因为可能begin和end都重合了，可能end还在往左走或begin还在往右走从而导致又不重合了，但我们要保证他们第一次重合后就不要再走了，因为此时的Key与重合位置一交换他左边一定比他都小，右边一定比他都大，已经可以了。故加个条件begin<end的前提下，两者才可移动。
整体排序的思路（类似于二叉树的前序遍历）：
单趟排序后，只要Key的左边和右边都有序了，整体是不是就是有序了。那Key的左边和右边要有序，可以再选一次Key1再次单趟排序，使Key1左边的都<Key1，Key右边的都>Key1，然后此时若Key1左边的有序，右边的也有序，整个就有序了，那对于Key右边的同理，选一个Key2再次单趟排序，而对于Key2本身的左边和右边又可以选一次Key3，不断递归下去，终止条件就是划分的只剩一个值了，一个值我们就可认为是升序了，就不用再往下划分了，直接递归往回返就能实现升序，即整体排序完毕。
快排的时间复杂度和空间复杂度分析：
时间复杂度最好的情况下是每次选的key都是中位数，而单趟排序的时间复杂度是O（N）（要看它的思想，不用看代码），因为begin往右走，end往左走，最后重合，相当于把整个数组走了一遍，所以为O（N）
时间复杂度最好的情况下：
时间复杂度最坏的情况下：
空间复杂度：O（logN） (以2为底，N的对数)
因为递归调用的空间复杂度是计算它的深度（每一层都要建立栈帧，而栈帧是要消耗空间），因为类似二叉树，故深度就可算出来。
缺陷：
实际当中无法保证选key是中位数，但我们可以考虑至少不要选到最大的或者最小的做key，当有序的情况下（一定是最坏的情况下），选到最大的或最小的值作为key效率不高，这种是运气很不好的情况下，一般的情况下都还很不错的。但严重的问题是面对有序的情况下需要建很多栈，而栈的空间本来就不大，堆的空间才大，如果数据很多就会导致栈溢出，程序崩溃，怎么解决呢？
三数取中：保证不要选到最小或者最大，让有序时变成最优。（即三个数中找中间数）
即最中间的数和最大的数和最小的数选择那个最中间的数作为key，但我们之前写的逻辑都是最后一个数作为key的，那就再把这个最中间的数和最后一个数换一下就行了。
意义：让原来不是二分->利用三数取中趋近二分->效率提高
三数取中只要在PartSort中改一下即可，三数取中让最坏的情况不再出现，时间复杂度不再看最坏，综合而言快排时间复杂度:O（N*logN）
跟左右指针法的思路差不多，也可以说比左右指针法好理解那么一点点
具体思路：
先利用三数取中方法把中间的数放在最后面
1、先将选定的基准值(最右边)直接取出，然后留下一个坑，
2、当左指针遇到大于key时，直接将该值放入坑中，而左指针指向的位置形成新的坑位，
3、然后右指针遇到小于基准值的数时，将该值放入坑中，右指针指向的位置形成坑位，
4、循环上述步骤，直到左右指针相等。最后将基准值放入坑位之中。
下图中先展示不用三数取中法的过程（若用了三数取中法key应=3）
代码简单，但不易理解。
具体思路：
1、选定基准值，定义prev和cur指针(cur = prev + 1)
2、cur先走，遇到小于基准值的数停下，然后将prev向后移动一个位置
3、将prev对应值与cur对应值交换
4、循环上面的步骤，直到cur出了数组范围
5、最后将基准值与++prev的对应位置交换
6、递归排序以基准值为界限的左右区间
最终代码改的就是PartSort3而已，QuickSort引用PartSort3函数
快排的一些优化：
在递归中，若递归到后面已没什么数据了，而你还在一直递归找key值往下划分，这样就会效率低下，而且建的栈也相对多了一些。
小区间使用插入排序排，不再使用快速排序的递归排，减少整体的递归次数。
非递归的意义：
1、提高效率（递归建立栈帧还是有消耗的，但对于现代计算机，这个优化微乎其微，可以忽略）
2、递归最大的缺陷：若栈帧的深度太深，可能导致栈溢出，因为系统栈空间一般不大，再兆(M)级别，数据结构栈模拟非递归，数据是存储在堆上的，堆是G级别的空间。
非递归的实现思路：
用栈来保存需要排序的左右区间，那肯定是先用左，再用右，那就要利用栈先进后出的性质，先利用的肯定是后入栈。
首先跟递归一样利用单趟排序，利用那三种方法哪种都行，所谓递归无非就在于他把区间不断递归划分然后找基准值key，那就让栈来做这件事就可实现非递归。每次利用栈先进后出的性质，把区间放入栈内并从栈中取出来
引申的总结：
递归改非递归（所有的递归都能改为非递归）
1、改为循环（如斐波那契数列），一般一些简单的递归才能改为循环
2、栈模拟存储数据非递归
代码模板如下：
归并排序的思想：
归并排序的单趟排序的思想，合并两段有序数组，合并以后依旧有序，在有序的前提下归并一次单趟排序就有序了。
但给你一个数组你无法保证它左右两端是有序的，那就把它的左端和右端分一半（n->n/2->n/4.....直到只剩一个数），并且一直分，直到剩一个数，一个数肯定是有序的，再往回归并即可（此时满足，左端和右端有序，只有整体不保证有序就可以用归并）
整个过程：分解（递归的过程）+ 合并（递归往回退）
整个递归过程类似于后序遍历（左右根），不会先合并，而是会一直往下分解，直到分解到剩一个数（即分割到不可分割时）才开始合并。
归并：（和之前讲过的合并两个有序的链表思路一样），对于两个有序的区间，从两个区间开头比（两个区间begin1和begin2分别指向开头，其实就是下标），建立一个tmp数组来存储，小的数放在tmp数组中，然后对应的小的数存在的区间下标++（即begin1++或者begin2++），另一个区间不动，然后再比较，还是两个区间中小的数放入tmp中，并且下标++......一直比，直到其中有一个区间走完了，再把另一个区间的数拷贝到tmp数组的后面，即整个tmp数组就是两端区间整体有序的合并，再拷贝回a数组中即可。
那为什么需要创建额外空间tmp数组？
在归并排序算法中，我们将待排序的数组分成两个子数组，然后分别对这两个子数组进行排序，最后将两个有序的子数组合并成一个有序的数组。
在合并两个有序的子数组时，我们需要使用一个临时数组来存储合并后的结果。这是因为在合并过程中，我们需要按照一定的顺序比较两个子数组中的元素，并将较小的元素依次放入临时数组中。如果直接在原始数组中进行合并操作，可能会导致元素的位置被覆盖，从而导致错误的排序结果。
通过使用临时数组，我们可以保证合并操作不会影响到原始数组中的元素位置，从而确保排序的正确性。在合并完成后，我们再将临时数组中的元素复制回原始数组的对应位置，完成整个归并排序过程。
因此，在归并排序中建立临时数组是为了保证合并操作的正确性和稳定性。
归并排序的时间复杂度和空间复杂度：
时间复杂度：O（N*logN）
本质上就跟二叉树一样，高度logN，而每一层都是N，故为N*logN
空间复杂度：O（N）（用空间换时间）
因开辟了额外的临时空间
归并排序的递归->非递归：可以用栈和队列，但是都不够好，因为他还有空间复杂度的消耗，这里递归改为非递归用迭代好一点。
思路：
理想情况下：
本质上gap控制的是几个数据合并，gap=1，就1个1个合。
那么对于代码实现，区间应该如何划分？
若用 for (int i = 0; i < n; i++)
一对就是两部分（两组）,每次都是一组一组来走，那每一组都对应一个由gap划分的区间
若为开区间则为：[i，i+gap) [i+gap，i+2*gap)
若为闭区间则为：[i，i+gap-1] [i+gap，i+2*gap-1]
因为我们之前写的归并代码是在闭区间的基础上写的，所以这里用闭区间的，并且我们把归并部分的代码单独放在一个函数中MergeArr以方便这里的非递归的归并。
执行结果如下：
如果把a数组的元素个数改为6，运行下代码，程序直接崩溃
故上述代码还存在问题，当元素个数是2的倍数时才会恰好排好序，本质上是因为gap每次都能正好把区间正好分为一半，因为gap每次都*=2，所以恰好分割时正好排好序，但不是2的倍数的情况下，比如只有6个元素，最终可能左边分为4个，右边分为两个才对，但代码中我们的区间范围会产生越界等问题，所以要考虑一下。
下面说的第一个，第二个数组是因为从左到右分对，一对有两部分，每部分又称为每个组，左面的那部分为第一组，右面那部分为第二组，每一组都是gap个数据。
1、第一个数组越界时，第二个数组不存在，所以不用合并，第一个数组本身就是有序数组
2、第二个数组完全越界时，第二个数组依然不存在，所以不用合并
3、部分组越界时，第二个数组存在但是不完整，此时我们将第二个数组的结束位置调整为原数组末尾位置即可，让第一个数组和第二个数组合并。
运行结果正确：
4、逆序对的个数
思路：
如果能统计数组中每个数出现的次数，就能把他们排出来。
效率很高，但是如果范围很大就会很费空间。计数排序针对一些特殊场景比较适用。适用于数据范围很集中，不适用于最大值与最小值相差特别大的那种，不然动态开辟会开辟很多空间。并且只适用于整形，如果是浮点型或字符串排序，还得用比较排序。
计数排序的时间复杂度和空间复杂度：
时间复杂度：O（N+range）(本来为2N，故约等于N)
空间复杂度：O（range）
1、掌握排序的实现
2、排序的时间复杂度和空间复杂度（要理解，不要硬背）
3、稳定性
4、排序之间特性的对比
归并文件排序（了解）我的另一篇博客有写
计数排序（了解）
最后：如果想测试各大排序的效率，可以用如下代码：