Java中排序算法有哪些

小编给大家分享一下Java中排序算法有哪些，相信大部分人都还不怎么了解，因此分享这篇文章给大家参考一下，希望大家阅读完这篇文章后大有收获，下面让我们一起去了解一下吧！

冒泡排序（Bubble Sort）

• 比较相邻的元素。如果第一个比第二个大，就交换它们两个，直到最后

• 算法分析

• 这里注意，如果发现没有交换，证明已经是排好序了

• 第一次比较就没有出现交换，所以是 O(n)   

• 最佳情况：T(n) = O(n)   

• 最差情况：T(n) = O(n2)   

• 平均情况：T(n) = O(n2)

选择排序（Selection Sort）

• 第一个分别与后面的进行比较，每次把最大（最小）的投出来

• 算法分析

• 最佳情况：T(n) = O(n2) 

• 最差情况：T(n) = O(n2)  

• 平均情况：T(n) = O(n2)

插入排序（Insertion Sort）

• 每次拿出一个与前面挨着的比较，发现第一个比自己大（小）的插入，前面的序列都是有序序列

•  算法分析

• 每次比较多少次不确定，近似n次

• 每次都不需要动（每次比较一次），遍历一次

• 最佳情况：T(n) = O(n)   

• 最坏情况：T(n) = O(n2)   

• 平均情况：T(n) = O(n2)

希尔排序（Shell Sort）

• 改进插入排序

• “缩小增量排序”或者“递减增量排序”

•  算法分析

• 基于插入排序的两点性质而来：

• 对一个“几乎”已经排好序的无序序列，插入排序的效率是很高的，可以达到线性排序的效率

• 最佳情况：T(n) = O(nlog2 n)  

• 最坏情况：T(n) = O(nlog2 n)  

• 平均情况：T(n) =O(nlog2n)　

• 时间复杂度：

归并排序（Merge Sort）

• 把长度为n的输入序列分成两个长度为n/2的子序列；

• 对这两个子序列分别采用归并排序；

• 将两个排序好的子序列合并成一个最终的排序序列。

• 算法分析

• 最后一轮访问是n

• 往前推每次都是n/2

• 取极限

• 最佳情况：T(n) = O(n)  

• 最差情况：T(n) = O(nlogn)  

• 平均情况：T(n) = O(nlogn)

快速排序（Quick Sort）

• 选择中间数，把大雨的丢右边，小于的丢左边

• 递归

• 算法分析

• 最佳情况：T(n) = O(nlogn)   

• 最差情况：T(n) = O(n2)   

• 平均情况：T(n) = O(nlogn)　

堆排序（Heap Sort）

• 算法分析

• 最佳情况：T(n) = O(nlogn)

• 最差情况：T(n) = O(nlogn)

• 平均情况：T(n) = O(nlogn)

计数排序（Counting Sort）

• 有确定范围的数

• 申请最大数长度的数组

• 算法分析

• 计数排序不是比较排序，排序的速度快于任何比较排序算法。

• 由于用来计数的数组C的长度取决于待排序数组中数据的范围

• 这使得计数排序对于数据范围很大的数组，需要大量时间和内存。

• 等于待排序数组的最大值与最小值的差加上1

• 当输入的元素是n 个0到k之间的整数时，它的运行时间是 O(n + k)。

• 最佳情况：T(n) = O(n+k)  

• 最差情况：T(n) = O(n+k)  

• 平均情况：T(n) = O(n+k)

桶排序（Bucket Sort）

• 桶排序是计数排序的升级版。

• 桶排序最好情况下使用线性时间O(n)，

• 因为其它部分的时间复杂度都为O(n)。

• 桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，

• 很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。

• 但相应的空间消耗就会增大。

• 最佳情况：T(n) = O(n+k) 

• 平均情况：T(n) = O(n+k)   

• 最差情况：T(n) = O(n2)　

基数排序（Radix Sort）

• 基数排序也是非比较的排序算法，对每一位进行排序，从最低位开始排序，复杂度为O(kn),为数组长度，k为数组中的数的最大的位数；

• 算法分析

• 最佳情况：T(n) = O(n * k)   

• 最差情况：T(n) = O(n * k)   

• 平均情况：T(n) = O(n * k)

以上是“Java中排序算法有哪些”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注亿速云行业资讯频道！

亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>