Java中排序算法有哪些

小編給大家分享一下Java中排序算法有哪些，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

冒泡排序（Bubble Sort）

• 比較相鄰的元素。如果第一個比第二個大，就交換它們兩個，直到最后

• 算法分析

• 這里注意，如果發(fā)現(xiàn)沒有交換，證明已經(jīng)是排好序了

• 第一次比較就沒有出現(xiàn)交換，所以是 O(n)   

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

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

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

選擇排序（Selection Sort）

• 第一個分別與后面的進行比較，每次把最大（最?。┑耐冻鰜?/p>

• 算法分析

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

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

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

插入排序（Insertion Sort）

• 每次拿出一個與前面挨著的比較，發(fā)現(xiàn)第一個比自己大（小）的插入，前面的序列都是有序序列

•  算法分析

• 每次比較多少次不確定，近似n次

• 每次都不需要動（每次比較一次），遍歷一次

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

• 最壞情況：T(n) = O(n2)   

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

希爾排序（Shell Sort）

• 改進插入排序

• “縮小增量排序”或者“遞減增量排序”

•  算法分析

• 基于插入排序的兩點性質(zhì)而來：

• 對一個“幾乎”已經(jīng)排好序的無序序列，插入排序的效率是很高的，可以達到線性排序的效率

• 最佳情況：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）

• 選擇中間數(shù)，把大雨的丟右邊，小于的丟左邊

• 遞歸

• 算法分析

• 最佳情況：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)

計數(shù)排序（Counting Sort）

• 有確定范圍的數(shù)

• 申請最大數(shù)長度的數(shù)組

• 算法分析

• 計數(shù)排序不是比較排序，排序的速度快于任何比較排序算法。

• 由于用來計數(shù)的數(shù)組C的長度取決于待排序數(shù)組中數(shù)據(jù)的范圍

• 這使得計數(shù)排序?qū)τ跀?shù)據(jù)范圍很大的數(shù)組，需要大量時間和內(nèi)存。

• 等于待排序數(shù)組的最大值與最小值的差加上1

• 當輸入的元素是n 個0到k之間的整數(shù)時，它的運行時間是 O(n + k)。

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

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

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

桶排序（Bucket Sort）

• 桶排序是計數(shù)排序的升級版。

• 桶排序最好情況下使用線性時間O(n)，

• 因為其它部分的時間復雜度都為O(n)。

• 桶排序的時間復雜度，取決與對各個桶之間數(shù)據(jù)進行排序的時間復雜度，

• 很顯然，桶劃分的越小，各個桶之間的數(shù)據(jù)越少，排序所用的時間也會越少。

• 但相應的空間消耗就會增大。

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

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

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

基數(shù)排序（Radix Sort）

• 基數(shù)排序也是非比較的排序算法，對每一位進行排序，從最低位開始排序，復雜度為O(kn),為數(shù)組長度，k為數(shù)組中的數(shù)的最大的位數(shù)；

• 算法分析

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

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

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

以上是“Java中排序算法有哪些”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業(yè)資訊頻道！