常见排序算法

插入排序是从数组的首元素开始，遍历整个数组，遍历到每个元素的时候，将这个元素依次和它前面的元素进行比较，如果按照从小到大的方式进行排序的话，要求前面的所有元素的值小于它本身，使用一个中间变量，将这个元素保存起来，将大于它的元素依次往后移，最后遇到和它一样大或者小于它的元素，将它放到这个元素的后面。所以排序过程中，需要一个临时的中间变量。

代码：

直接插入排序特性总结：

1、元素集合越接近有序，直接插入排序的时间复杂度越低。

2、时间复杂度：O(N^2)。

3、空间复杂度：O(1),它是一种稳定的排序算法。

4、稳定性：稳定

希尔排序也是一种插入排序，是插入排序后的种更加高效的排序方式，由于插入排序，被排序序列越有序插入排序越快。

图片来自 https://blog.csdn.net/dujiafengv/article/details/102599103

代码：

 希尔排序特性总结：

1、希尔排序是对直接插入排序的优化

2、当排序步长都>1的排序都是预排序，目的是让数组更加接近有序，当步长==1的时候，数组已经很接近有序了，这样排序的速度就很快了。

3、希尔排序的时间复杂度不确定，经过推导出来的时间复杂度为O(N^1.3-N^2)。

4、稳定性：不稳定。

代码：

直接选择排序的特性总结：

1、直接选择排序的算法效率不高，实际很少使用。

2、时间复杂度O(N^2)。

3、空间复杂度：O(1)。

4、稳定性：不稳定。

堆排序是借助一种特殊的数据结构来排序的，要使用堆，首先需要建堆，堆在逻辑上是一颗完全二叉树，在内存中是一个数组（数组是按照二叉树的层序遍历存储的）。堆只分为大顶堆或者小顶堆，建堆的过程需要用到自顶向下调整算法。

自顶向下调整算法：

 更加详细的建堆过程 https://blog.csdn.net/weixin_43447989/article/details/99695304

建立好大顶堆或者小顶堆以后，就可以进行堆排序了。

方式是，依次将堆顶的元素与堆尾的元素交换，交换后的堆尾作为有序区不再参与堆的自顶向下调整算法。可以发现，要得到递增序列初始的堆必须为大顶堆，递减序列，初始的堆为小顶堆。

代码：

建堆的过程需要的时间复杂度是O(logn),堆排序最坏的情况是排N次，所以堆排序的时间复杂度是O(Nlogn)，堆排序仅仅需要一个记录原始堆大小的辅助变量。

堆排序的特性分析：

1、使用堆排序来选择第几大的数很好用。

2、时间复杂度：O(logn)。

3、空间复杂度：O(1)。

4、稳定度：不稳定。

基本思想： 基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排
序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

代码：

 对于冒泡排序相信大家都比较熟悉，它的核心思想是，假如是将数组从大到小排序，外层for循环执行一次，数组中最大的那个数将向前移一位。所以外层for循环的循环次数最多是数组的的元素个数次。而内层for循环的循环次数如for (j = 0; j < (MAX-1) - i; j++)//此处的MAX-1-i不是MAX-i的原因是j+1不会越界，因为后面会有a[j+1]和a[j]的判断。

冒泡排序的特性分析：

1、时间复杂度：O(N^2)。

2、空间复杂度：O(1)。

3、稳定度：稳定。

6.1、                                                                                    hoare法

实现步骤：

    第一步：选择待排序数组中的三个值，分别是首尾还有中值，start，end 和mid
    第二步：对三个数进行排序，从小到大，
    第三步：保护基准值，swap(src + mid, src + end - 1);也就是基准值和倒数第二个元素交换
    第四步：a = start + 1, b = end - 2，b向前找比基准值小的，a向后找比基准值大的，找到之后 交换所指向的值，然后将基准值和a指向的值交换 （因为是从小到大排序a找的大的，应该在数组后面所以基准值和它换），产生左边的都比基准值小，右边的都比基准值大，然后a作为二叉树的根返回，重复上面四步操作，直到类似形状的二叉树被遍历完为止。 

6.2                                                                     双指针法

双指针法：

从小到大

    第一步：定义两个指针一个指向数组头a一个指向数组尾b；
    第二步：以头指针为基准值先从尾指针开始向前找比基准值小的元素，找的之后交换a，b所指向的值
    第三步：此时b所指向的值就是基准值，a开始向后找，找到比基准值大的交换。
    第四步：完成一次交换之后，以基准值下标为返回值返回递归调用点
 

更好理解的双指针版快速排序

 挖坑法：https://blog.csdn.net/weixin_43447989/article/details/100054493

快速排序的特性总结：

1、快速排序的综合性能和使用场景都是很好的，所以叫快速排序。

2、时间复杂度，排一次的时间复杂度是O(logn),最坏的情况下排n次，所以整体时间复杂度是O(n*logn)。

3、空间复杂度：O(logn)。

4、稳定性：不稳定。

图片来自https://blog.csdn.net/doubleguy/article/details/81390951

可以看到归并排序的基本方法是先对数组执行分的操作，将数组分割成二叉树的样子，再对其进行排序。

图片来自https://blog.csdn.net/weixin_44465743/article/details/88902052

从上面的分治图中可以总结出规律：将数组细分为最小单元时，形状像一颗二叉树，并且它的排序方式和二叉树的后序递归遍历很像，我们尝试着使用二叉树的后序递归遍历解决基本的代码框架。

二叉树的后序遍历是：

代码实现：

归并排序特性分析：

1、归并排序需要额外的空间开销。

2、时间复杂度：O(nlogn)。

3、空间复杂度O(N)

4、稳定性：稳定。