常见排序算法总结 - Java 实现

た入场券 2021-08-20 00:52 327阅读 0赞

点击上方 [Java后端][Java]，选择 设为星标

优质文章，及时送达![format_png][]

作者 | 小蓝

来源 | 蓝桥（id:lanqiaocenter）

![format_png 1][]

**排序算法可以分为两大类：**

1、**非线性时间比较类排序**：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序。

2、**线性时间非比较类排序**：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。

![format_png 2][]

相关概念

*  稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
 *  不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
 *  时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
 *  空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。

一、插入排序

1.1直接插入排序

插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。

直接插入排序的算法思路：

1、设置监视哨temp，将待插入记录的值赋值给temp；

2、设置开始查找的位置j；

3、在数组arr中进行搜索，搜索中将第j个记录后移，直至temp≥arr\[j\]为止；

4、将temp插入arr\[j+1\]的位置上。

![format_png 3][]

**1.2 希尔排序**

希尔排序(Shell's Sort)是插入排序的一种，又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。

希尔排序的算法思路：

1、把数组按下标的一定增量分组；

2、对每组使用直接插入排序算法排序；

3、随着增量逐渐减少，每组包含的值越来越多，当增量减至1时，整个文件被分成一组，算法便终止。

![format_png 4][]

**二、交换排序**

**2.1 冒泡排序**

在一组数据中，相邻元素依次比较大小，最大的放后面，最小的冒上来。

冒泡排序算法的算法思路：

1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。

2.对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

3.针对所有的元素重复以上的步骤，除了最后一个。

4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

![format_png 5][]

**2.2 快速排序**

快速排序（Quicksort）是对冒泡排序的一种改进。

通过一次排序将数组分成两个子数组，其中一个数字的值都比另外一个数字的值小，然后再对这两子数组分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

快速排序的算法思路：（分治法）

1.先从数列中取出一个数作为中间值middle；

2.将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边；

3.对左右两个小数列重复第二步，直至各区间只有1个数。

![format_png 5][]

![format_png 6][]

**三、选择排序**

**3.1 简单选择排序**

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

简单选择排序的算法思路：

1.首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置

2.再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾

3.以此类推，直到所有元素均排序完毕。

![format_png 7][]

**3.2 堆排序**

堆排序（英语：Heap Sort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。在堆的数据结构中，堆中的最大值总是位于根节点（在优先队列中使用堆的话堆中的最小值位于根节点）。

堆排序的算法思路：

1.最大堆调整（Max Heapify）：将堆的末端子节点作调整，某个节点的值最多和其父节点的值一样大；

2.创建最大堆（Build Max Heap）：将堆中的所有数据重新排序,堆中的最大元素存放在根节点中；

3.堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算。

![format_png 8][]

![format_png 9][]

![format_png 4][]

**四、归并排序**

**4.1 二路归并排序**

归并排序（mergeSort）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

若将两个有序表合并成一个有序表，称为二路归并。例如：将2个有序数组合并。比较2个数组的第一个数，谁小就先取谁，取了后就在对应数组中删除这个数。然后再进行比较，如果有数组为空，那直接将另一个数组的数依次取出即可。

二路归并排序的算法思路：

1、将数组分成A，B 两个数组，如果这2个数组都是有序的，那么就可以很方便的将这2个数组进行排序。

2、让这2个数组有序，可以将A，B组各自再分成2个数组。依次类推，当分出来的数组只有1个数据时，可以认为数组已经达到了有序。

3、然后再合并相邻的2个数组。这样通过先递归的分解数组，再合并数组就完成了归并排序。

![format_png 10][]

![format_png 11][]

![format_png 12][]

**五、计数排序**

计数排序（Counting sort）不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

计数排序的算法思路：

1、求出待排序数组的最大值 max 和最小值 min。

2、实例化辅助计数数组temp，temp数组中每个下标对应arr中的一个元素，temp用来记录每个元素出现的次数。

3、计算 arr 中每个元素在temp中的位置 position = arr\[i\] - min。

4、根据 temp 数组求得排序后的数组。

![format_png 13][]

![format_png 14][]

**六、桶排序**

桶排序 (Bucket sort)的工作原理是将数组分到有限数量的桶里。每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））。但桶排序并不是比较排序，他不受到 O(n log n) 下限的影响，桶排序可用于最大最小值相差较大的数据情况。

桶排序的算法思路：

1、找出待排序数组中的最大值max和最小值min；

2、我们使用动态数组ArrayList 作为桶，桶里放的元素也用 ArrayList 存储。桶的数量为 (max-min) / arr.length + 1；

3、遍历数组 arr，计算每个元素 arr\[i\] 放的桶；

4、每个桶各自排序；

5、遍历桶数组，把排序好的元素放进输出数组。

![format_png 15][]

![format_png 16][]

**七、基数排序**

基数排序（radix sort）是桶排序的扩展，基本思想是将整数按位数切割成不同的数字，然后按每个位数分别比较。

基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。基数排序的算法思路：

1、取得数组中的最大数，并取得位数；

2、arr为原始数组，从最低位开始取每个位组成radix数组；

3、对radix进行计数排序（利用计数排序适用于小范围数的特点）。

![format_png 17][]

![format_png 18][]

![format_png 19][]

![format_png 20][]

。

--------------------

【END】

如果看到这里，说明你喜欢这篇文章，请 **转发** **、点赞**。微信搜索「web\_resource」，关注后回复「进群」或者扫描下方二维码即可进入无广告交流群。**↓扫描二维码进群↓**![format_png 21][]

--------------------

**推** **荐** **阅** **读 *****1.***  [一千行 MySQL 学习笔记][MySQL]***2.***    [一份工作坚持多久跳槽最合适？][Link 1]***3.***  [项目中常用到的  19 条 MySQL 优化][_19 _ MySQL]***4. *** *** *** [零基础认识 Spring Boot][Spring Boot]

***5.***  [团队开发中 Git 最佳实践][Git]

![format_png 22][]

**喜** **欢** **文** **章** **，** **点** **个** **在看 ** ![format_png 23][]

[Java]: https://blog.csdn.net/qq_37217713/article/details/101445094
[format_png]: /images/20210731/3294e7b748384fe2af391907b484742c.png
[format_png 1]: /images/20210731/6a0d20879fc54eb18022e4c8f3cbf0ac.png
[format_png 2]: /images/20210731/f89bd1f26982442fb6f28665b1f61519.png
[format_png 3]: /images/20210731/b4c37617b3f343babc6c144c67203bb8.png
[format_png 4]: /images/20210731/750ec7112ca143deb4717e67e873dd5a.png
[format_png 5]: /images/20210731/f70f219e71e94f55ae6e67006684585f.png
[format_png 6]: /images/20210731/ac0bd95483264bd3bcf5bb14a275b6e1.png
[format_png 7]: /images/20210731/f261571d6d824909a4336470b89384f7.png
[format_png 8]: /images/20210731/a833a61660f94f069c6263488f95b9ea.png
[format_png 9]: /images/20210731/880a3595b5ff4a35b839007635196826.png
[format_png 10]: /images/20210731/b457d8a238c143dfa21d7042c7874fe9.png
[format_png 11]: /images/20210731/3c723d0aebfc420aa21abc7aeae8cf77.png
[format_png 12]: /images/20210731/29396b7a10dd4ba8b74671fb8535e52d.png
[format_png 13]: /images/20210731/d0db08defac644988cec6698e0faff9d.png
[format_png 14]: /images/20210731/ceb33c09b16443578f293a09771abf90.png
[format_png 15]: /images/20210731/18199246523448e7b300a8a3791a18e8.png
[format_png 16]: /images/20210731/2a030b4e44ff48e7a9983f9bb84a9333.png
[format_png 17]: /images/20210731/4d0bb180693545e69bb6d82d5fb584e4.png
[format_png 18]: /images/20210731/f02816af13c448c7a9cb98a7dcf59eff.png
[format_png 19]: /images/20210731/99695f71a0a04e6189f38e85a0582d0c.png
[format_png 20]: /images/20210731/07610461df024bcebdd8b61a195643a4.png
[format_png 21]: /images/20210731/7e77c31160cb4086abe3a51c40f1d072.png
[MySQL]: https://blog.csdn.net/qq_37217713/article/details/102658688
[Link 1]: https://blog.csdn.net/qq_37217713/article/details/103170812
[_19 _ MySQL]: http://mp.weixin.qq.com/s?__biz=Mzg2MjEwMjI1Mg%3D%3D&chksm=ce0dac08f97a251e8c47234958fd73a0e1eaf56f62fa9c86b5a7f28ead87ab3dec24c9192b18&idx=2&mid=2247490443&scene=21&sn=cd85b69365d3062af8682de713fff9a0#wechat_redirect
[Spring Boot]: https://blog.csdn.net/qq_37217713/article/details/103094622
[Git]: https://blog.csdn.net/qq_37217713/article/details/102481709
[format_png 22]: /images/20210731/28faa89feb3943ec9da5ba90c27d392f.png
[format_png 23]: /images/20210731/8cf02a25e9e44a1b8840d7d5b73e071f.png