![]()
![]()
1.排序的概念：所谓的排序就是对于一组记录，按照某个或者某些关键字，递增或递减的排序这些记录。
2.排序的分类：此文章将会介绍四类排序。
一、插入排序：直接插入排序、希尔排序。
二、选择排序：选择排序、堆排序。
三、交换排序：冒泡排序、快速排序。
四、归并排序：归并排序。
3.排序稳定性概念介绍：一组的记录当中肯定是会出现相同数值的情况，在一开始的时候虽然数值相同，但是这些相同数值的数据是有顺序的，看一个排序算法是否具有稳定性，看的就是在排序之后，这些数值相同的数据的顺序有没有变化，顺序有变化就说明这个排序算法不具有稳定性，顺序没有变化就说明该排序算法具有稳定性。
4.七个排序的详情介绍：
1.直接插入排序（升序版）：在生活当中，我们在打牌时，对于牌的有序整理就是直接插入排序的具体体现。思路详解：有一组数据在数组当中存储，我们默认第一个数为有序的，然后从他后面的数开始，先用一个变量把数据值保存，把这个数值在数组中对应的位置空出来，我们需要拿着这个数值和他前面的值一次进行比较，比较会出现两种情况：一、比前面的值小，前面的值要往后挪动到空位，又有新的空位，更新一下空位以及继续要比较的前一个数；二、比前一个值大，就把变量存的值放进此时的空位里。代码实现：![]()
。直接插入排序的时间复杂度虽然是O（n^2），有点高，但是他是具有实践意义的，因为在库里的快排的小区间优化采用的就是直接插入排序。直接插入排序的稳定性：稳定的，因为他是一一向前比较的，在不满足条件的时候，直接放在使他不满足条件的数值的后面。
2.希尔排序：希尔排序其实是直接插入排序的优化版本，他是很快的，优化完可以跟快排、堆排坐一个桌子了。怎么个优化方式呢？通俗来说，就是先进行对数据的预处理，预处理完事之后，再来一次直接插入排序完成排序，因为在预处理完事之后，待排序的数据是很接近有序的，而直接插入排序在对于接近有序的数据时，效率是很可观的。之前预处理其实也是用的直接插入排序，但是预处理时，待排序的数据间隔至少是为一的，不然数据就是紧挨着的，那么跟进行一次普通的直接插入排序就没有区别了，预处理就起不到优化的作用了。预处理采用对一组一组间隔相等的数据排序，如果间隔大，那么在前面的大数值的数据就能够很快速的跳到后面，而后面的小数值的数据也能够快速跳到前面；间隔小，只是数据跳的速度慢了一点，不过同样是具有优化作用的。代码实现：有两种写法：一是把间隔不同的当作一组，这样的一组一组来预处理；二就是每组并排走（因为间隔不同的一组的小组的排头是一次顺序又循环的）。一、![]()
；二、![]()
。间隔gap:其实间隔gap的取法有多种，我们代码实现当中采用的是一种相对权威的一种。希尔排序的稳定性：不稳定，因为在预处理时，会分为多组间隔不同的待排序的记录，而数值相同的数据显然不会被全部分到一组间隔相同的一组记录当中。
3.选择排序：思路详解：在一个待排序的数组当中，会把数组分成两边，一边是已经排好的有序区间，另一边是待排序区间，我们要从待排序区间里面选择最大或者是最小的数据，把选出的数据放进有序区间内。代码实现：是优化版本的选择排序，在同一待排序区间内，选出最大值以及最小值，两头齐开，![]()
，代码实现注意图中标红。选择排序的稳定性：不稳定，最大值、最小值的取到相同数值的数据会交换到有序区间里面，数值相同的数据的顺序可能会变。
4.堆排序：思路详解：堆排序是利用数据结构堆的特性和其中两个重要的算法为地基的一个排序算法，（向上调整算法![]()
and向下调整算法![]()
）。要想让数据从大到小排序，那么就要建立小堆；想让数据从小到大排序，则需要建立大堆，（因为在这个算法里对于数组区间的划分是左边是待拿出来排序的堆数据，右边是排好的有序区间，拿出堆顶元素放在有序区间、从右往左填数，堆的大小也在同步收缩）。然后运用向上调整算法建堆，或者是运用向下调整算法建堆（从第一个非叶子节点开始执行）。运用堆的特性，取出堆顶元素，然后把他交换到数组的最后一个位置（堆的最后一个叶子节点），然后在这个叶子节点之前的数据都是还没有排序的，把他们用向下调整算法调整成堆，然后继续之前的操作。这一整个操作都是在顺序存储的数组上直接进行的，所以，排完序之后，数组就是有序的了。代码实现：![]()
~堆排序的稳定性：不稳定，因为堆排序对于数据的处理其实是有两步的，一步是把数据全部放进堆数据结构里面，二是要拿堆顶元素出来放到有序区间里面，这两步会影响到同值数据的顺序。
5.冒泡排序：冒泡排序客观来说是没有实践意义的，但是有教学意义。思路详解：冒泡的核心是交换，如果既定是升序（小到大），把待排序数据的区间比作一个湖，左边就是湖底，右边就是湖面，冒泡排序的每一趟把此时数据中最大的数据通过两两比较再交换的方式送其至湖面。代码实现：![]()
~冒泡排序的稳定性：稳定的，一趟一趟两两交换，只交换想要的。
6.快速排序：快速排序的内容比较多，简述一下此次文章涵盖的内容：递归和非递归；单趟排序的三种版本：hoare版本、挖坑法、前后指针法；两种优化方式：三数取中法选key、小区间优化。找工作时，优化方式口述就行。接下来介绍一下递归+hoare的组合：思路详解：![]()
，单趟的hoare版本是默认最左边的数为key，右指针先走找他想要找的值，找到后停下，让左指针走，找左指针想要找的值，找到后进行交换，此为一次，后面都是循环此次，直到相遇（右指针找到想找的值，停下，左指针是因为遇到右指针才停下的）；使用左右指针向中间靠拢，左边找比key大的，右边找比key小的，排个升序，一定一定是右指针先走，最左边为key，右指针就得先走，才能保证左右指针相遇的格子的值比key小，好跟key位置的值做交换（如果选择最右边为key，左指针一定先走，才能保证左右指针相遇的格子的值比key大，好跟key位置的值做交换）。递归就是不断把区间缩小（单趟结束之后总可以把区间划分成 [left, key - 1] key [key + 1, right] ），默认key位置是排好序了，然后两边区间像第一次的情况处理，先单趟再划分区间递归（宏观角度：再次调用函数，相信这个函数能自己完成），直到区间不能再缩，此时就是递归出口。代码实现（递归+hoare的组合）：![]()
。再来介绍一下递归+前后指针组合：思路详解：![]()
，借助前后指针，一开始前指针指向key，后指针指向key+1位置，后指针指到的如果是小于key的值，前后指针都需要++，后指针指到的是大于key的值，后指针++，知道后指针越界，此时结束单趟。递归都是一样的，只是单趟不同。代码实现：![]()
。挖坑法：不做代码实现，讲一下思路：![]()
，同样是左右双指针，先将第一个数值存进变量key里面，让该位置格子可以填值，一个指针指向这里，另一个指针用来找可以填的值，找到后把值填到坑里，填完之后，刚刚找到值的位置就形成新的坑位了，那么另一个指针就要找可填值了，如此循环，直到两指针相遇，把变量值填入；这几乎和hoare版本的单趟是一样的，一个采用临时变量，一个没有罢了。到这，我们来介绍一下两种优化方式：首先介绍一下三数取中法选key，由于一些极端情况，会导致选这个key值会让时间复杂度较高，我们就可以通过三数取中，选取较为均衡的值来当key值，避免极端key值带来的麻烦，我们是在最左边的值、最右边的值、中间值，这三个值中选取大小在中间的值。三数取中代码实现：![]()
；我们再来介绍一下小区间优化，由于我们上述的快排是用递归实现的，这就会有递归太深，栈溢出的风险，所以我们就可以在递归区间较小的时候，不再继续调用快排函数，反而使用其他排序直接进行对区间的排序工作，这时候直接插入排序的实践意义就体现出来了，库里面的快排小区间优化用的就是直接插入排序。小区间优化代码实现：![]()
。最后我们来讲一下非递归的形式是怎么实现的，因为笔试可能考，有必要总结归纳一下：快排的非递归的实现是借助栈来模拟实现的，函数栈帧的每一次调用，跟新的都是区间，只有区间有变化，所以栈数据结构里面维护的数据就是区间，栈的先进后出能很好的模拟递归栈帧的创建、返回等等。非递归的代码实现：![]()
。快速排序的稳定性：不稳定，在对区间排序时，会对数据进行交换，远距离交换，不在乎同值数据的顺序的。 其实还有一个实现方式，参考荷兰国旗问题，在这就不多赘述了。
7.归并排序：递归形式思路详解：归并排序和快速排序一样，都是划分区间，对区间进行整理，但是归并排序有点略微不同，他是先把区间划分到最小情况，然后在递归返回的时候进行对两个区间为一组的合并+排序。递归形式的代码实现：![]()
。非递归形式的思路详解：归并排序的非递归的模拟实现就借助不了栈模拟了，因为麻烦，对于归并排序的非递归的模拟实现我们会采用循环的方式来实现：我们定义一个变量gap来表示向上合并时数据的个数，对于同一个gap我们采用循环的方式来两两向上合并（这是模拟递归的一层），gap模拟的其实是递归层数（深度），然后处理一下最后合并的边界，因为不可能总是数据数相同、偶数对偶数的合并，也可能是：假设最后两个区间分别为：q1 : [l1, r1]、q2 : [l2, r2]；第一种情况：r2越界，第二种情况：l2、r2越界，第三种情况r1、l2、r2越界。处理完这三种越界情况非递归归并排序就通用了，处理这三种情况时，也能很好体现在每次合并就把区间拷贝回原数组的好处了（省事，特判剪枝掉就行）。代码实现：![]()
、![]()
。归并排序的稳定性：稳定，不存在在排序时对数据进行远距离交换。
