🚩排序可谓是老生常谈了，在这里，我给大家带来一些常用的排序算法。🚩常用的排序算法有八个：直接插入排序，希尔排序，选择排序，堆排序，冒泡排序，快速排序(快排)，归并排序，计数排序。每一个排序算法都有其独特的思想，我们不仅要学会它的思想，还要能够在合适的场景中选出合适的排序算法。因此，这一块，要很熟练很熟练。🚩本章所有的排序均以升序为例来讲解，弄懂了升序，降序也是不在话下。
直接插入排序其实我们从小就在接触了，我们之前打的跑得快，斗地主，抓牌整理牌的过程就是类似于插入排序。
对于插入排序，它的过程是如何的呢？我们以下面这组乱序数组为例（假设这里以升序为例）：
由于数组的第一个元素是有序的，所以我们要从数组的第二个元素开始，也就是从下标为1的元素开始执行插入排序。
当插入第i (i >= 1) 个元素时，前面的array[0],array[1],…,array[i-1] 已经排好序，此时将array[i] 的值与array[ i - 1 ] , array[ i - 2 ] , … 的值依次进行比较，比array[i]大就将其往后移，找到正确的插入位置将array[i] 插入即可。
当i为1时 （定义一个变量tmp存储此时要插入的值，再定义一个变量end指向要插入的元素的前一个位置），也就是上面数组对元素1的插入，此时将1与前面一个元素5比较，发现5比1大，这时就将5后移放在1的位置，此时前面的有序序列已经遍历完毕，将tmp放入正确的位置，1就插入完毕。1插入后，数组变为：1 5 2 4 6 3，此时对元素2（下标也为2）进行插入，同样的进行上面的操作，5被挪动到下标为2的位置，5处理完后，元素2与元素1比较，1 < 2，此时说明数组已经有序，然后将元素2插入到元素1的后面的位置就OK了。2插入完后数组变为：1 2 5 4 6 3，同样的，后面对元素4，6，3的插入也是如此，由后向前依次与前面的有序序列的元素进行比较，比较出无序就将被比较的元素往后挪动一个位置，比较出有序，说明该元素应该被插入在被比较的元素的后面。
图示：
动图演示：
代码实现：
对于直接插入排序的时间复杂度，从最坏的角度看，每一趟插入的次数相加是一个等差数列，因此直接插入排序的时间复杂度为 ==O(logN^2)==。而最好的情况，就是数组有序，此时每一个元素的插入排序都不会进行，所以相当于只是遍历了一遍数组，时间复杂度为==O(N)==。
很明显，空间复杂度为 ==O(1)==。
直接插入排序是稳定的。（除排序交换了两个元素的初始相对位置顺序之外，并没有改变其它任意两个元素初始的相对位置（开始谁在前，现在还是谁在前）。）
希尔排序是直接插入排序的一个优化版。
那么它是如何优化的呢?
希尔排序法又称缩小增量法。希尔排序法的基本思想是：一个数组，它的长度为n，先选定一个整数gap（gap < n），把待排序的数组的所有元素分成若干个组，所有距离为gap的分在同一组内，并对每一组内的元素进行距离为gap的插入排序。当一个gap排完每一组后，gap按一定规律变小，并重复上述分组和排序的工作。当gap == 1时，相当于直接插入排序，最后数组就有序了。
图示排序过程：
每个gap值都对应着一趟距离为gap的插入排序，每一趟排序会使数组越来越接近有序，直到最后gap为1，相当于是一趟直接插入排序。当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，就会很快。这样整体而言，可以达到优化的效果。
关于gap，每次排完一趟到下一趟排序可以将他除以2作为这趟排序的分组排序距离，这样循环往复，最终，gap会变成1，数组会有序。
代码实现：
稳定性：不稳定。
基本的选择排序思路如下：
每一次从数组的待排序的数据元素中找出最小或者最大的元素放在起始位置，直到所有待排序的数据元素放在应在的位置为止。
代码实现（这里以升序为例）：
测试：
（以升序为例）
图示：
由上面的分析可以知道，我们需要两个指针指向未排序序列的两端，每次未排序序列两边缩小1，都需要遍历一遍未排序序列找最小最大值往两边甩，这样从两端开始向内逐渐有序，最终数组就会有序。
代码实现（这里以升序为例）：
对于选择排序的时间复杂度，为 ==O(N ^ 2)==，优化与不优化都是如此，每次放置一个元素或者两个元素到有效的位置都需要遍历数组，第一次可能是 n - 1 次，第二次就是 n - 2，依次类推，就是一个等差数列，所以为==O(N ^ 2)==。那最好的情况呢？如果此时数组已经有序，它还是要跟不有序一样依次遍历数组，老实的很捏，所以还是==O(N ^ 2)==，这也就是选择排序是八大排序中最烂排序的原因。
而空间复杂度毫无疑问是==O(1)==。
对数组排序，首先就是要对这个数组建堆，如果是要将数组升序，就建为大堆，如果是要将数组降序，就建为小堆。
如何建堆？我们从最后一个结点的父节点开始，依次执行向下调整算法，直到根节点执行完全后，便建成了堆。当然我们也可以从第二个结点开始，依次执行向上调整算法，直到最后一个结点执行完后便建成了堆，不过这样的时间复杂度为O(n * logn)，而前面的向下调整算法的方式的时间复杂度为O(n)，所以这里我们采用向下调整算法的方式来建堆。至于这两个调整算法的时间复杂度是如何计算出来的，这里就不做讨论，它的本质其实是有关数列求和的计算。
对于向下调整算法，我们先要找到该结点（假设下标为parent）的孩子结点，而孩子结点又分为左孩子结点（下标为parent * 2 + 1）和右孩子结点（下标为parent * 2 + 2），所以我们需要找出两个孩子结点当中较大的那个，如果该节点的数据比较大的那个孩子结点的数据要小，那就进行交换，然后循环往复继续向下寻找孩子结点重整堆。
整个操作，我们可以先比较两个孩子的大小找出大的那个，然后在与大的这个孩子结点进行比较，如果父结点比他小（以大堆为例），说明这个孩子结点该上位了。然后继续向下执行这个操作。
向下调整算法代码实现（这里以升序为例）：
有了建堆的认识，后面的操作也不难了，只不过需要注意几个细节。
当数组建成大堆形式后，堆顶元素是最大的，此时我们可以将堆顶元素与最后一个元素进行交换，这样最大的元素就到了数组的末尾了。然后我们对这个处在数组最后一个位置的最大元素视而不见，将交换过去的堆顶元素执行向下调整算法，这时，第二大的元素就到了堆顶，然后此时的堆顶元素继续与最后一个元素进行交换 （注意第一个交换过去的最大的元素已经不在范围内了，也就是说每将一个当前最大的数交换过去后，可视作n(数组的长度)减一一次） ，然后再将交换过去的堆顶元素执行向下调整算法......这样循环往复，最终该数组就变成了升序。
堆排序整体代码实现：
堆排序的时间复杂度为 ==O(N * logN)==：排序前对数组建堆的向下调整算法整个过程为O(N)，后面排序阶段的操作相当于遍历了一遍数组，每一次都需要从根节点(数组开头)执行一次向下调整算法，因此排序阶段的时间复杂度为==O(N * logN)==，所以整体就是==O(N * logN)==。而最好的情况也是==O(N * logN)==，可以说，堆排序也是很老实的，尽管数组开始有序，在建堆的过程中，就先需要将数组打乱，后面的操作也就一样了。
堆排序没有创建额外的空间，所以空间复杂度为==O(1)==。
冒泡排序的过程就跟冒泡一样（这话好像并没什么卵用），每次都是相邻两个元素进行比较，如果前面一个元素比后面一个元素数据大，就将这两个元素进行交换，然后继续比对下一组相邻的元素，一趟过后，最大的那个元素会处在数组的最后一个位置。到了下一趟排序，第二大的元素就会到数组的倒数第二个位置，再下一趟就是第三大的元素到正确的位置，接着就是第四大，第五大，直到数组有序为止。
这里的每一趟排序都有一个元素到达正确的位置，也就是说，每次排完一趟后，下一趟需排序的元素就要减一。所以这里我们可以控制每趟排序相邻两个元素比较的次数以及总共要排的趟数：假设数组的元素个数为n，那么总共只需要排n - 1趟即可（因为排完n - 1次后，n - 1个元素都到了正确的位置，那么剩下的那个元素肯定也是到达了正确的位置），而每一趟排序，因为是两两比较，所以只需要比较该趟排序的元素个数减一次。有了这样的控制，我们只需要两个for循环即可完成。
图示理解冒泡排序:
代码实现:
hoare版本的快速排序为什么叫hoare呢？因为快速排序就是由Hoare于1962年提出的一种二叉树结构的交换排序方法。 此实现方法也可以说是开山鼻祖。
霍尔法动图过程展示
【核心思路】：任取待排序元素序列中的某元素作为基准值（一般我们选择取最左边），按照该排序码将待排序集合分割成两个子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程（递归），直到所有元素都排列在相应位置上为止。
【整个过程】：我们取最左边的数为一个基准值，然后两个指针分别从序列的两端开始走。右边先走，找比基准值小的数，然后左边再走，找比基准值大的数，两个指针都找完后，交换两个指针指向的值，这个意思就是：将比基准值小的数往前放置，比基准值大的数往后放置，直到两个指针相遇，再将基准值与相遇的这个位置的值交换（这个基准值就到了正确的位置，不用再改了），此时整个序列被分割成两个子序列，左边的序列都是比基准值小的数，右边的序列都是比基准值大的数，然后分别递归左序列和右序列，依次这样操作，最终，整个序列就会变得有序。
图示：
第一趟排序，对整个序列进行上述操作：
然后以排完第一趟的6的位置为基准，分别递归左和右：
代码实现：
一个问题？为什么要右边先走呢？
实际上，如果取最左边的值为基准值，就右边先走；如果取最右边的值为基准值，就左边先走；我们拿右边先走的例子来说：如果取最左边的值为基准值让右边先走，会发现，两个指针相遇的位置的值始终是比基准值小的，最后与基准值交换后正好符合规律，小的值往左边放。如果左边先走的话，相遇的位置的值是始终都比基准值大的，这就不符合规律了（当然有一种情况是：基准值是最大的数，左边先走的话会一直走到底，最终还是将小的数换过来了，不过经过三数取中优化后，这种情况不会出现）。
① 直接将最左端的值选出来作为key值，然后 ==【右边找小】== ，放入坑位，然后更新坑位值为右侧找到的那个数所在的下标；
② 出现了新的坑位后，==【左边找大】== ，找到之后将数字放到新的坑位中，然后继续更新坑位。
③ 循环往复上面的步骤，直到两者相遇为止，更新相遇处为最新的坑位，然后将key值放入坑位即可，保证左边比key小，右边比key大。
【整个过程】： 以最左边的值为基准值，以最左边的位置为第一个坑位，然后右边开始找小，找到后将这个小于基准值的数放入当前的坑位，然后更新坑位为当前右边找到的那个小的数的位置。接着左边开始找大，找到后将这个大于基准值的数放入当前的坑位，然后更新坑位为当前左边找到的那个大的数的位置。这样循环往复，直到左指针和右指针相遇，相遇的这个位置就是最新的坑位，最后将基准值放入这个坑位，再递归左序列和右序列即可。
动图过程展示
代码实现：
动图过程展示
这种方法被叫做【前后指针法】是因为该方法定义的两个指针都从序列的左边开始走，由于限制条件不同，因此两个指针走的速度也不同，所以被称之为【前后指针法】。
整体思路：
定义一个prev指针位于起始端，再定义一个cur指针就位于它的后方，记录当前 位置上的key值。
cur指针向后找比key小的值，若是找不到，则一直++；若是cur找到了比key 小的值，prev++，然后交换二者的值之后cur再++。
直到cur超过右边界之后，退出循环逻辑，将此时prev位置上的值与key值做一个交换，保证左边比key小，右边比key大。
一过程如图：
代码实现：
在子序列比较小的时候，其实插排是比较快的，因为对于有序的序列，插排可以达到O(n)的复杂度，如果序列比较小，则和大序列比起来会更加有序，这时候使用插排效率要比快排高。其实现方法也很简单：快排是在子序列元素个数变成1时才停止递归，我们可以设置一个阈值n，假设为10，则大于10个元素，子序列继续递归，否则选用插排。（其实在C++的STL中，归并算法就是采用了这个思路，当子序列小到一定程度的时候，直接选用插排对子序列进行排序）
快排是在待排数列越趋近于有序时变得越慢，复杂度越高，调用插排可以很好的解决这个问题。
快速排序最优的情况就是每一次取到的元素都刚好平分整个数组(很显然我上面的不是)；
最差的情况就是每一次取到的元素就是数组中最小/最大的，这种情况其实就是冒泡排序了(每一次都排好一个元素的顺序)
空间复杂度
其实这个空间复杂度不太好计算，因为有的人使用的是非就地排序，那样就不好计算了（因为有的人用到了辅助数组，所以这就要计算到你的元素个数了）；我就分析下就地快速排序的空间复杂度吧；
首先就地快速排序使用的空间是O(1)的，也就是个常数级；而真正消耗空间的就是递归调用了，因为每次递归就要保持一些数据；
最优的情况下空间复杂度为：O(logn) ；每一次都平分数组的情况最差的情况下空间复杂度为：O( n ) ；退化为冒泡排序的情况
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
归并排序体现了一个很重要的思想：分治思想。
归并可以理解为先递归在合并。
将数组以类似二叉树的形式一直分，一分二，二分四，四分八......直到最后分到只有一个元素，由于一个元素可以看作是有序的，所以从最后的一个元素开始，依次有序合并并返回。
归并思想：
合并过程：
动图过程展示
代码实现：
非递归实现的思想与递归实现的思想是类似的。
既然是非递归，那当然只有循环才可以解决。
这里我们先1个元素为一组，两组为一个合并组依次进行合并；然后再以2个元素为一组，两组为一个合并组依次进行合并........往后每次一组的元素个数都是上一次的一组的元素个数的两倍。
当然，待排序序列的元素个数并不一定是2的次方数，所以这里需要对每两组合并的序列进行一个区间合理范围判断，以此来处理越界或者某些其它的问题。
整个过程图示如下：
代码实现（C语言）：
==Counting Sort== 计数排序，顾名思义，就是统计待排序数组元素的出现次数。其基本思想比较简单：
动图过程展示
代码实现（C语言）：
缺陷：
如下图：
Sort.h
sort.c
stack.c
test.c
小结：
【==直接插入排序==】：使用得比较广泛，虽属于O(N2)的排序算法，但是在数据接近有序时能体现出优势，需要掌握。
【==希尔排序==】：看起来不起眼，但是性能不错，平均时间复杂度也能达到O(NlogN)，至于O(N1.3)了解一下即可，主要还是记住它排序的这个过程。
【==选择排序==】：如果能想得起其他排序算法，就不要用这个了,在各种场合测试下它都是最差劲的，无论如何都是在选数然后交换的过程。
【==堆排序==】：性能不错，重点掌握的是【向下调整算法】以及如何建堆的过程，在数据量特大的情况下可以使用。
【==冒泡排序==】：大学生最喜欢用排序算法，性能不高，只有在序列已然有序或者接近有序的情况下才能展现出优势。
【==快速排序==】：综合性能最优，包含【左右指针法】【挖坑法】【前后指针法】【三路划分法】(本文没提供)，学有余力都应掌握，重点在理解Hoare版本的思路。对于要参加校招的同学还要求掌握非递归的写法。
【==归并排序==】：即使内排序也是排序，性能较高又可以达到稳定，常用于文件外排序。也有递归和非递归两种写法，最好是都要掌握。
💝掌握八大排序，排序这一块就够用了，当然还有桶排序，基数排序，文件外排序之类的，大家可以查阅相关资料进行学习。❤️🔥后续将会继续输出有关数据结构与算法的文章，你们的支持就是我写作的最大动力！