*常见排序算法代码实现及特性分析*
原创
*常见排序算法代码实现及时间复杂度分析*
*注释：截图只是排序代码实现的部分，基于面向对象的思想，我定义了一个接口Sort，里面只有一个抽象方法operate(int[] array)，具体的排序算法均实现（implements）该接口。
一、直接插入排序
1.基本思想：
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到全部插入完为止，得到一个新的有序序列。
有序序列区间：[0,i)
无序序列区间：[i,array.length)
*图解来源：https://blog.csdn.net/llzk_/article/details/51628574
2.代码实现：
3.特性总结：
（1）使用场景：数据量较小，且元素集合越接近有序，此算法时间效率越高；
（2）稳定性：稳定（即排序前后相同元素值的前后位置不会改变，代码中的体现就是第2个for循环中的条件“array[j] > val”，相等时并不往后移，故保证了稳定性）；
（3）平均时间复杂度：O(N^2)；
（4）最好时间复杂度：O(N)，所排数组已经全部有序，只需进行N次比较；
（5）最坏时间复杂度：O(N^2)，所排数组是倒序排列，第N个元素需要（N-1）次比较操作和N次移位操作，操作次数总共为N(N-1)/2 + N(N+1)/2，故时间复杂度为O(N^2)；
（6）空间复杂度：O(1)，并未聚集性开辟额外空间，只有常量级的临时空间。
二、希尔排序（又称缩小增量排序）
1.基本思想：
希尔排序本质是对直接插入排序的改进，先选定一个整数gap = array.length / 2(取值不固定，但有优劣区别)，对待排序数据进行分组，所有距离为gap的数据在同一组，并对每一组内的数据进行直接插入排序，然后取gap = gap / 2重复上述分组和排序工作，当gap == 1时，所有数据在同一组，此时数据已接近有序，进行最后一次直接插入排序，只需微调就可全部有序。
*图解来源：https://www.cnblogs.com/chengxiao/p/6104371.html
2.代码实现：
3.特性总结：
（1）使用场景：专家们提倡，几乎任何排序工作在开始时都可以用希尔排序，若在实际使用中证明它不够快，再改成快速排序这样更高级的排序算法（来自百度百科）；
（2）稳定性：不稳定（由于希尔排序属于跳跃式分组，故排序后可能将相同元素值的位置颠倒）；
（3）时间复杂度分析：希尔排序的时间的时间复杂度为O(N^3/2)，希尔排序时间复杂度的下界是(N*log2N)。希尔排序没有快速排序算法快 O(N*(logN))，因此中等大小规模表现良好，对规模非常大的数据排序不是最优选择。但是比O(N^2)复杂度的算法快得多。此外，希尔算法在最坏的情况下和平均情况下执行效率相差不是很多，与此同时快速排序在最坏的情况下执行的效率会非常差。（来自百度百科）；
（4）空间复杂度：O(1)，类似直接插入排序，只是分组进行插入而已。
三、冒泡排序
1.基本思想：
在无序区间，从前往后通过相邻数据的比较，将最大值冒泡到无序区间的最后（也可以从后往前比较将最小值冒泡到无序区间的最前面），持续这个过程，直到数据整体有序。
有序区间：[array.length - i - 1,array.length)
无序区间：[0,array.length - i -1)
*图解来源：百度图片冒泡排序图解过程
2.代码实现：
3.特性总结：
（1）使用场景：适用于N较小的情况；
（2）稳定性：稳定（相邻数据比较时只有前者大于后者时才进行交换，相等不会进行交换，故排序前后相同元素值的相对位置不改变）
（3）平均时间复杂度：O(N^2)，外层循环执行(N-1)次，内层循环最多执行N次，最少执行1次，平均执行(N+1)/2次，故总共执行比较交换次数为(N-1)*(N+1)/2 = (N^2 - 1)/2，去掉常数和最高项系数即为O(N^2)；
（4）最好时间复杂度：O(N)，元素已经有序时，外层循环只执行一次就会结束，实际进行了（N-1）次比较，去掉常数即为O(N)；
（5）最坏时间复杂度：O(N^2)；
（6）空间复杂度：已经有序时最优为0，逆序时最坏O(N)，平均O(1)，只有交换时用到额外空间。
四、简单选择排序
1.基本思想：
每次从无序区间选择最小（最大）的元素，放在无序区间的最前（最后），直到全部排完。
有序区间：[0,i)
无序区间：[i,array.length)
*图解来源：百度图片简单选择排序过程
2.代码实现：
3.特性总结：
（1）使用场景：适用于N较小的情况，时间复杂度和输入无关；
（2）稳定性：不稳定（比如序列6 8 6 5 1 9，第一遍选择最小的1会和第一个6进行交换，那么原序列中2个6的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法）；
（3）时间复杂度：O(N^2)，无论原数据是否有序，都需要将无序区间全部遍历比较，然后进行交换，当无序区间长度为N时，需要进行(N-1)次比较和1或0次交换，总共比较次数为0+1+2+3+...+(N-1) = N * (N-1) / 2，故时间复杂度为O(N^2)；
（4）空间复杂度：O(1)
五、快速排序（重要）
1.基本思想：
快速排序是对冒泡排序的一种改进，从待排序区间选择一个基准值（pivot），接着在方法partiton中通过与基准值的比较将小于等于基准值的放在左边，大于等于基准值的放在右边，返回基准值所在的下标，采用分治思想，对左右两个小区间采用同样的方式进行处理，直到小区间长度等于1（表示已经全部有序）或等于0（表示已经没有需要处理的数据）。
*图解来源：百度图片快速排序图解过程
2.代码实现：
3.特性总结：
（1）使用场景：快速排序整体的综合性能和使用场景都是比较好的，大多数情况下适用；
（2）稳定性：不稳定（每次都要根据基准值对元素进行两两交换操作，故不能保证稳定性）；
（3）平均时间复杂度：O(N*(logN));
（4）最好时间复杂度：O(N*(logN)),
推理如下：
*来源：https://blog.csdn.net/weixin_41725746/article/details/93080926
（5）最坏时间复杂度：O(N^2)，即退化成冒泡排序，每次取到的基准值都是区间里的最大（或最小），这样每次都只能调整好一个数据；
（6）空间复杂度：O(logN)，快速排序的空间消耗主要是递归调用的地方。
六、堆排序（重要）
1.基本思想：
基本原理也是选择排序，只是不再使用遍历来选择无序区间的最值，而是通过建堆来选择（并非真的定义节点以及左右子树，而是通过下标来反应“父子”关系）。
*注：排升序建大根堆，排降序建小根堆
*图解来源：百度图片堆排序图解过程
2.代码实现：
3.特性总结：
（1）使用场景：没有特定场景；
（2）稳定性：不稳定（交换数据的时候，是父节点和子节点进行比较，具有跳跃性）；
（3）时间复杂度：推理如下：
*来源：https://blog.csdn.net/weixin_41725746/article/details/93080926
（4）空间复杂度：O(1)，常量级的临时空间。
七、归并排序（重要）
1.基本思想：
归并排序也是分治思想的一个典型应用，是建立在归并操作上的一种有效的排序算法，将已经有序的子序列进行合并，得到完全有序的序列，即先使每个子序列有序，再使子序列段间有序。（将两个有序表合并成一个有序表，称为二路归并）
*图解来源：百度图片归并排序图解过程
2.代码实现：
3.特性总结：
（1）使用场景：如果需要保证稳定性，且空间不强求，可以选用；
（2）稳定性：稳定（采用二分法就近分割，元素相对位置并不会改变）；
（3）时间复杂度：O(N*(logN))，归并排序的执行效率与原始数组的有序程度无关，任何情况下都是O(N*(logN))，推理如下：
由于归并排序采取分而治之的思想，所以时间复杂度也可以进行分解为两倍的子排序时间复杂度T(N/2)加上本次归并过程的时间复杂度即
O(N) = 2 * O(N/2) + N => 2^k * O(N / 2^k) + k * N，当子问题分解为一个元素时，N / 2^k = 1，（层数）k = logN，进而得出
O(N) = N + 3 * N * logN = N*(logN)；
（4）空间复杂度：O(N)，二路归并时需要开辟额外的数组空间来进行排序，然后有序地搬移回原数组中。
*注：
归并排序本质是一种外部排序，有时，待排序的文件很大，计算机内存不能容纳整个文件，这时候对文件就不能使用内部排序了（其实所有的排序都是在内存中做的，这里说的内部排序是指待排序的内容在内存中就可以完成，而外部排序是指待排序的内容不能在内存中一下子完成，它需要做内外存的内容交换），外部排序常采用的排序方法也是归并排序。
小结：
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。